链表浅谈

发表于 分类于 阅读次数：

链表介绍

  • 增加了虚拟头结点，即在索引0前面还有头结点，只需要遍历index次就可到达index的位置。
  • 使用了内部类，即Node类

基本实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
public class LinkedList_New<E> {
	class Node {
		private E e;
		private Node next;

		public Node(E e, Node next) {
			this.e = e;
			this.next = next;
		}

		public Node(E e) {
			this(e, null);
		}

		public Node() {
			this(null, null);
		}

		@Override
		public String toString() {

			return e.toString();
		}
	}

	public int size;
	public Node dummyhead;// 虚拟头结点

	public LinkedList_New() {
		size = 0;
		dummyhead = new Node(null, null);
	}

	public int getSize() {
		return size;
	}

	public boolean isEmpty() {
		return size == 0;
	}

	//向头结点插入元素，则关键在于i
	public void add(int index, E e) {
		if (index < 0 || index > size) {
			throw new IllegalArgumentException("add failed");
		}
		Node prev = dummyhead;
		for (int i = 0; i < index; i++) {
			prev = prev.next;
		}
		Node node = new Node(e);
		node.next = prev.next;
		prev.next = node;
		size++;
	}

	// 在链表头添加新的元素e
	public void addNode(E e) {
		add(0, e);
		// Node node=new Node(e.head);
	}

	// 在链表尾部添加新的元素e，其中链表长度大于链表尾部的索引，在循环结束时，prev指针恰好指在链表的末尾处。
	public void addLast(E e) {
		add(size, e);
	}

	// 获得链表index位置的元素，其中和add函数的区别是add函数中需要知道该元素的前一个头结点，而获取值只需要从当前的正常节点开始。
	//假如链表长度为4，起始位置是i=0处，循环3次。
	public E get(int index) {
		if (index < 0 || index > size) {
			throw new IllegalArgumentException("add failed");
		}
		Node curr = dummyhead.next;
		for (int i = 0; i < index; i++) {
			curr = curr.next;
		}
		return curr.e;
	}

	public E getFirst() {
		return get(0);
	}

	public E getLast() {
		return get(size - 1);
	}

	// 修改链表第index位置的元素值为e
	public void set(int index, E e) {
		if (index < 0 || index > size) {
			throw new IllegalArgumentException("add failed");
		}
		Node curr = dummyhead.next;
		for (int i = 0; i < index; i++) {
			curr = curr.next;
		}
		curr.e = e;
	}

	// 查找链表中是否包含元素e
	public boolean contains(E e) {
		Node curr = dummyhead.next;
		while (curr != null) {
			if (curr.e.equals(e)) {
				return true;
			}
			curr = curr.next;
		}
		return false;
	}

	// 因为也涉及到前一个元素的指针，所以从dummyhead开始
	public E delete(int index) {
		if (index < 0 || index > size) {
			throw new IllegalArgumentException("add failed");
		}
		Node prev = dummyhead;
		// 先进行for循环,一直到index位置，将要删除的节点的指针指向前一位。
		for (int i = 0; i < index; i++) {
			prev = prev.next;
		}

		Node deleteNode = prev.next;
		prev.next = deleteNode.next;
		deleteNode.next = null;
		size--;
		return deleteNode.e;
	}

	public void deleteFirst() {
		delete(0);
	}
	//删除最后一个元素时，prev指针应位于倒数第二个元素上
	public void deleteLast() {
		delete(size - 1);
	}

	@Override
	public String toString() {
		StringBuilder stringBuilder = new StringBuilder();
		Node curr = dummyhead.next;
		for (Node i = curr; i != null; i = i.next) {
			stringBuilder.append(i + "->");
		}
		stringBuilder.append("NULL");
		return stringBuilder.toString();
	}
}

测试示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class LinkedListTest {

	public static void main(String[] args) {
		LinkedList_New linkedList=new LinkedList_New();
		for(int i=0;i<5;i++) {
			linkedList.addNode(i);
			System.out.println(linkedList);
		}
		linkedList.add(2, 66);
		System.out.println(linkedList);
		linkedList.delete(3);
		System.out.println(linkedList);
		linkedList.deleteFirst();;
		System.out.println(linkedList);
		linkedList.deleteLast();;
		System.out.println(linkedList);
	}
}

输出示例

1
2
3
4
5
6
7
8
9
0->NULL
1->0->NULL
2->1->0->NULL
3->2->1->0->NULL
4->3->2->1->0->NULL
4->3->66->2->1->0->NULL
4->3->66->1->0->NULL
3->66->1->0->NULL
3->66->1->NULL

链表实现栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class LinklistStack<E> implements Stack<E> {
	private LinkedList_New list;
	public LinklistStack() {	
		this.list = new LinkedList_New();
	}
	@Override
	public int getSize() {
		return list.getSize();
	}
	@Override
	public boolean isEmpty() {
		return list.isEmpty();
	}
	@Override
	public void push(E e) {
		list.addNode(e);;		
	}
	@Override
	public E pop() {
		return list.deleteFirst();
	}
	@Override
	public E peek() {
		return list.getFirst();
	}
	@Override
	public String toString() {
		StringBuilder stringBuilder=new StringBuilder();
		stringBuilder.append("Stack: top ");
		stringBuilder.append(list);
		return stringBuilder.toString();
	}
}

性能比较

与数组实现的栈进行入栈出栈的性能比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.Random;

public class StackTimeTest {
	public static double QueueTest(Stack s,int count) {
		long start=System.currentTimeMillis();
		Random random=new Random();
		for(int i=0;i < count;i++) {
			s.push(random.nextInt(Integer.MAX_VALUE));
		}
		for(int i=0;i < count;i++) {
			s.pop();
		}
		long end=System.currentTimeMillis();
		return (end-start)/1000.0;
	}	
	public static void main(String[] args) {
		int count=10000;
		double time1=QueueTest(new LinklistStack(), count);
		System.out.println("LinklistStack: "+time1+"s");
		double time2=QueueTest(new ArrayStack(), count);
		System.out.println("ArrayStack: "+time2+"s");	
	}	
}

结果显示

1
2
LinklistStack: 0.006s
ArrayStack: 0.002s

LinklistStack中包含更多的new 操作，增加了一定的时间复杂度。

0%