数据结构——链表

继上一章的数组后,介绍第二个线性结构链表,链表相对于数组来说,优于增删,数组优于查。下面就来看看这个链表的链在何处?

链式结构(链表),数组不好的地方在于它需要先申请一个固定大小的空间,没有动态性,在Java的数据结构中ArrayList实现了可变长的数组,实际上就是当长度不够的时候重新申请一块原空间1.5倍大小的新空间,再把当前的元素全部拷贝过去。链式结构在这里进行了改进,它不需要元素是在一块连续的空间内的,它只需要一个指向下一个元素的位置的地址,Java中指向下一个元素的位置的方法是使用引用,链式结构虽然解决了动态性,但是对于查找来说却不太友好,降低了随机访问的效率,因为要在链表中查找一个元素,就必须从头开始遍历,直到找到那个元素。后面的一些非线性的数据结构比如树、队列、栈都用到了链表,当然也可以使用数组来实现,就看在什么应用场景下针对不同的需求来完成了,链表有单向、双向、循环,下面就来实现一个单向链表:

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
package top.devonte.structure.linear;

public class LinkedStructure {

/**
* 单向链表,创建一个1/2/3/4的单向链表,并输出
*/
public static void singleLinkedList() {
Node head = new Node(1, new Node(2, new Node(3, new Node(4, null))));
Node cur = head;
while (cur != null) {
System.out.print(cur.val + "\t");
cur = cur.next;
}
}

/**
* 双向链表,链表能够访问前一个元素,也能访问后一个元素。(用最垃圾的代码演示)
*/
public static void channelLinkedList() {
ChannelNode four = new ChannelNode(4, null);
ChannelNode three = new ChannelNode(3, four);
four.pre = three;
ChannelNode two = new ChannelNode(2, three);
three.pre = two;
ChannelNode head = new ChannelNode(1, two);
two.pre = head;
ChannelNode cur = head;
while (cur != null) {
System.out.print(cur.val + "\t");
cur = (ChannelNode) cur.next;
}
System.out.println();
cur = four;
while (cur != null) {
System.out.print(cur.val + "\t");
cur = cur.pre;
}
}

public static void main(String[] args) {
channelLinkedList();
}

static class ChannelNode extends Node {
ChannelNode pre;
public ChannelNode(int val, Node next) {
super(val, next);
}
}

static class Node {
int val;
Node next;
public Node(int val, Node next) {
this.val = val;
this.next = next;
}
}

}

结语

链表就是一个线性结构的补充,与数组互补,这个结构使用起来特别灵活,在一些算法里面如果不熟悉链表的话,很容易将引用指向错误的地方导致死循环,并且树结构就是使用链表的方式实现的,后面会对树进行一个详细的解释,因此学好链式结构有益于后面学习树。到这里两个基本的线性结构就已经讲完了,剩下的栈和队列都是对链表和数组的运用,使用了一种特殊限制来达到栈和队列的作用。下一章将对栈进行总结。