Fork me on GitHub

数据结构-链表

前面创建的动态数组, 栈和队列底层都是依托于静态数组的,靠resize来解决容量问题.而链表是真正的动态数据结构.

创建一个链表

链表的数据存储在节点(Node)中

1
2
3
4
class Node{
E e;
Node next;
}

最后一个节点的next指向null,链表相较于数组来说,丧失了随机访问的能力,但是却是真正的动态,不需要处理固定容量的问题

链表节点

新建一个LinkedList

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
public class LinkedList<E> {

private class Node{
public E e;
public 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();
}
}

}

添加元素

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
public class LinkedList<E> {

private class Node{
...
}

// 这里使用虚拟头结点, 接下来的增删改查操作将会方便很多
private Node dummyHead;
private int size;

public LinkedList(){
dummyHead = new Node();
size = 0;
}

// 获取链表中的元素个数
public int getSize(){
return size;
}

// 返回链表是否为空
public boolean isEmpty(){
return size == 0;
}

// 在链表的index(0-based)位置添加新的元素e
public void add(int index, E e){

if(index < 0 || index > size)
throw new IllegalArgumentException("Add failed. Illegal index.");

Node prev = dummyHead;
for(int i = 0 ; i < index ; i ++)
prev = prev.next;

prev.next = new Node(e, prev.next);
// 等价
// Node node = new Node(e);
// node.next = prev.next;
// prev.next = node;
size ++;
}

// 在链表头添加新的元素e
public void addFirst(E e){
add(0, e);
}

// 在链表末尾添加新的元素e
public void addLast(E e){
add(size, e);
}
}

修改元素

1
2
3
4
5
6
7
8
9
10
// 修改链表的第index(0-based)个位置的元素为e
public void set(int index, E e){
if(index < 0 || index >= size)
throw new IllegalArgumentException("Set failed. Illegal index.");

Node cur = dummyHead.next;
for(int i = 0 ; i < index ; i ++)
cur = cur.next;
cur.e = e;
}

重写toString方法进行测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    @Override
public String toString() {
StringBuilder res = new StringBuilder();

// Node cur = dummyHead.next;
// while(cur != null){
// res.append(cur + "->");
// cur = cur.next;
// }
for (Node cur = dummyHead.next; cur != null; cur = cur.next)
res.append(cur + "->");
res.append("NULL");

return res.toString();
}

查询元素

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
// 获得链表的第index(0-based)个位置的元素
public E get(int index){

if(index < 0 || index >= size)
throw new IllegalArgumentException("Get failed. Illegal index.");

Node cur = dummyHead.next;
for(int i = 0 ; i < index ; i ++)
cur = cur.next;
return cur.e;
}

// 获得链表的第一个元素
public E getFirst(){
return get(0);
}

// 获得链表的最后一个元素
public E getLast(){
return get(size - 1);
}

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

删除元素

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
// 从链表中删除index(0-based)位置的元素, 返回删除的元素
public E remove(int index){
if(index < 0 || index >= size)
throw new IllegalArgumentException("Remove failed. Index is illegal.");

Node prev = dummyHead;
for(int i = 0 ; i < index ; i ++)
prev = prev.next;

Node retNode = prev.next;
prev.next = retNode.next;
retNode.next = null;
size --;

return retNode.e;
}

// 从链表中删除第一个元素, 返回删除的元素
public E removeFirst(){
return remove(0);
}

// 从链表中删除最后一个元素, 返回删除的元素
public E removeLast(){
return remove(size - 1);
}

// 从链表中删除元素e
public void removeElement(E e){

Node prev = dummyHead;
while(prev.next != null){
if(prev.next.e.equals(e))
break;
prev = prev.next;
}

if(prev.next != null){
Node delNode = prev.next;
prev.next = delNode.next;
delNode.next = null;
size --;
}
}

编写main函数进行测试

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
import java.util.Random;

public class Main {

public static void main(String[] args) {

LinkedList<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < 5; i++) {
linkedList.addFirst(new Random().nextInt(10));
System.out.println(linkedList);
}

linkedList.add(2, 666);
System.out.println(linkedList);

linkedList.remove(2);
System.out.println(linkedList);

linkedList.removeFirst();
System.out.println(linkedList);

linkedList.removeLast();
System.out.println(linkedList);
}
}

结果

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

时间复杂度分析

  • 添加操作

    • addLast(e) O(n)
    • addFirst(e) O(1)
    • add(index, e) O(n/2) = O(n)
  • 删除操作

    • removeLast() O(n)
    • removeFirst() O(1)
    • remove(index) O(n/2) = O(n)
  • 修改操作

    • set(index, e) O(n)
  • 查找操作

    • get(index) O(n)
    • contains O(n)
  • 如果只对链表头进行操作,复杂度是O(1)

使用链表实现栈

直接使用之前创建的栈接口即可
因为栈只能从一端进行操作,这里使用链表头作为栈顶
创建LinkedListStack类, 实现栈的接口方法, 并进行简单测试

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
public class LinkedListStack<E> implements Stack<E> {
private LinkedList<E> list;

public LinkedListStack() {
list = new LinkedList<>();
}

@Override
public int getSize() {
return list.getSize();
}

@Override
public boolean isEmpty() {
return list.isEmpty();
}

@Override
public void push(E e) {
list.addFirst(e);
}

@Override
public E pop() {
return list.removeFirst();
}

@Override
public E peek() {
return list.getFirst();
}

@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("Stack: top ");
res.append(list);
return res.toString();
}

public static void main(String[] args) {

LinkedListStack<Integer> stack = new LinkedListStack<>();

for (int i = 0; i < 5; i++) {
stack.push(i);
System.out.println(stack);
}

stack.pop();
System.out.println(stack);
}
}

运行结果

1
2
3
4
5
6
Stack: top 0->NULL
Stack: top 1->0->NULL
Stack: top 2->1->0->NULL
Stack: top 3->2->1->0->NULL
Stack: top 4->3->2->1->0->NULL
Stack: top 3->2->1->0->NULL

链表栈和数组栈对比

编写一个main函数进行测试

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
import java.util.Random;

public class Main {

// 测试使用stack运行opCount个push和pop操作所需要的时间,单位:秒
private static double testStack(Stack<Integer> stack, int opCount) {

long startTime = System.nanoTime();

Random random = new Random();
for (int i = 0; i < opCount; i++)
stack.push(random.nextInt(Integer.MAX_VALUE));
for (int i = 0; i < opCount; i++)
stack.pop();

long endTime = System.nanoTime();

return (endTime - startTime) / 1000000000.0;
}

public static void main(String[] args) {

int opCount = 50000000;

ArrayStack<Integer> arrayStack = new ArrayStack<>();
double time1 = testStack(arrayStack, opCount);
System.out.println("ArrayStack, time: " + time1 + " s");

LinkedListStack<Integer> linkedListStack = new LinkedListStack<>();
double time2 = testStack(linkedListStack, opCount);
System.out.println("LinkedListStack, time: " + time2 + " s");
}
}

1
2
ArrayStack, time: 7.5600347 s
LinkedListStack, time: 14.0287178 s

两者的时间复杂度是一样的, 但是运行的时间却是不一样的
其实这个时间比较很复杂,jdk, LinkedListStack中包含更多的new操作, 机器性能等等

使用链表实现队列

在实现队列前,需要对链表进行改造
在链表头进行操作时时间复杂度是O(1)级别的,是因为对头节点进行了标记,如果对链表尾节点也进行标记,这样在链表尾进行添加操作时也可以通过标记直接添加, 时间复杂度也是O(1)级别的

但是这样的话在链表尾部删除元素时时间复杂度依然是O(n)级别的, 根据队列的性质, 我们可以从链表尾部添加元素(入队), 在链表头部进行删除元素(出队), 这样时间复杂度都是O(1)级别的了

创建LinkedListQueue类, 实现之前的Queue接口, 进行简单的测试

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
public class LinkedListQueue<E> implements Queue<E> {

private class Node{
public E e;
public 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();
}
}

private Node head, tail;
private int size;

public LinkedListQueue(){
head = null;
tail = null;
size = 0;
}

@Override
public int getSize(){
return size;
}

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

@Override
public void enqueue(E e){
if(tail == null){
tail = new Node(e);
head = tail;
}
else{
tail.next = new Node(e);
tail = tail.next;
}
size ++;
}

@Override
public E dequeue(){
if(isEmpty())
throw new IllegalArgumentException("Cannot dequeue from an empty queue.");

Node retNode = head;
head = head.next;
retNode.next = null;
if(head == null)
tail = null;
size --;
return retNode.e;
}

@Override
public E getFront(){
if(isEmpty())
throw new IllegalArgumentException("Queue is empty.");
return head.e;
}

@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append("Queue: front ");

Node cur = head;
while(cur != null) {
res.append(cur + "->");
cur = cur.next;
}
res.append("NULL tail");
return res.toString();
}

public static void main(String[] args){

LinkedListQueue<Integer> queue = new LinkedListQueue<>();
for(int i = 0 ; i < 10 ; i ++){
queue.enqueue(i);
System.out.println(queue);

if(i % 3 == 2){
queue.dequeue();
System.out.println(queue);
}
}
}
}

运行结果

1
2
3
4
5
6
7
8
9
10
11
12
13
Queue: front 0->NULL tail
Queue: front 0->1->NULL tail
Queue: front 0->1->2->NULL tail
Queue: front 1->2->NULL tail
Queue: front 1->2->3->NULL tail
Queue: front 1->2->3->4->NULL tail
Queue: front 1->2->3->4->5->NULL tail
Queue: front 2->3->4->5->NULL tail
Queue: front 2->3->4->5->6->NULL tail
Queue: front 2->3->4->5->6->7->NULL tail
Queue: front 2->3->4->5->6->7->8->NULL tail
Queue: front 3->4->5->6->7->8->NULL tail
Queue: front 3->4->5->6->7->8->9->NULL tail

三种队列对比

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
import java.util.Random;

public class Main {

// 测试使用q运行opCount个enqueueu和dequeue操作所需要的时间,单位:秒
private static double testQueue(Queue<Integer> q, int opCount){

long startTime = System.nanoTime();

Random random = new Random();
for(int i = 0 ; i < opCount ; i ++)
q.enqueue(random.nextInt(Integer.MAX_VALUE));
for(int i = 0 ; i < opCount ; i ++)
q.dequeue();

long endTime = System.nanoTime();

return (endTime - startTime) / 1000000000.0;
}

public static void main(String[] args) {

int opCount = 100000;

ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
double time1 = testQueue(arrayQueue, opCount);
System.out.println("ArrayQueue, time: " + time1 + " s");

LoopQueue<Integer> loopQueue = new LoopQueue<>();
double time2 = testQueue(loopQueue, opCount);
System.out.println("LoopQueue, time: " + time2 + " s");

LinkedListQueue<Integer> linkedListQueue = new LinkedListQueue<>();
double time3 = testQueue(linkedListQueue, opCount);
System.out.println("LinkedListQueue, time: " + time3 + " s");
}
}

运行结果

1
2
3
ArrayQueue, time: 76.0986852 s
LoopQueue, time: 0.0206508 s
LinkedListQueue, time: 0.0129043 s

主要差异:
ArrayQueue出队的时间复杂度是O(n)级别的,再加上外层的循环就是O(n^2)级别的了,所以对于ArrayQueue来说,testQueue方法的时间复杂度是O(n^2)级别的;
LoopQueue出队的时间复杂度是O(1)级别的, 再加上外层的循环就是O(n)级别的了,所以对于LoopQueue来说,testQueue方法的时间复杂度是O(n)级别的;
LinkedListQueue队列出队的时间复杂度是O(1)级别的, 再加上外层的循环就是O(n)级别的了,所以对于LinkedListQueue来说,testQueue方法的时间复杂度是也是O(n)级别的;

完整代码

-------------本文结束感谢您的阅读-------------
坚持原创技术分享,您的支持将鼓励我继续创作!
0%