数据结构之链表

雨点打透心脏的1/2处 2022-02-05 05:07 325阅读 0赞

数据结构链表的学习,以及如何用链表实现一个栈：

## 链表 ##

数组要一块连续的内存空间来存储，对内存的要求比较高。如果我们申请一个100MB大小的数组，当内存中没有连续的、足够大的存储空间 时，即便内存的剩余总可用空间大于 100MB，仍然会申请失败。  
链表恰恰相反，它并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用，所以如果我们申请的是 100MB 大小的链表，根本不会有问题。

![20190504172620.png][]

链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点 的地址。如图所示，我们把这个记录下个结点地址的指针叫作后继指针 next。

### 单链表 ###

![20190504172746.png][]

其中有两个结点是比较特殊的，它们分别是第一个结点和最后一个结点。我们习惯性地把第一个结点叫作头结点，把最后一个结点叫作尾结点。其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是：指针 不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点。与数组一样，链表也支持数据的查找、插入和删除操作。只不过效率会不高。

![20190504174653.png][]

### 循环链表 ###

![20190504174905.png][]

循环链表是一种特殊的单链表。它跟单链表唯一的区别就在尾结点：单链表的尾结点指针指向空地址，表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。

### 双向链表 ###

![20190504175352.png][]

双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性。那相比单链表，双向链表适解决删除结点中“值等于某个给定值”的结点，删除给定指针指向的结点。

### 双向循环链表 ###

![20190504175412.png][]

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

## 代码实现 ##

### 单链表实现 ###

<table> 
 <tbody> 
 <tr> 
 <td><pre>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 150 </pre></td> 
 <td><pre>public class LinkedList&lt;E&gt; {
 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 dummyHead; private int size; public LinkedList() {
 dummyHead = new Node(null, null); size = 0; } public int getSize() {
 return size; } public boolean isEmpty() {
 return size == 0; } //为链表头添加新的元素E public void addFirst(E e) {
 add(0, e); } //在链表的index(0-based)位置添加新的元素e //链表中不是一个常用的操作 public void add(int index, E e) {
 if (index &lt; 0 || index &gt; size) {
 throw new IllegalArgumentException("Add Failed.Illegal index."); } Node prev = dummyHead; for (int i = 0; i &lt; index; i++) {
 prev = prev.next; } prev.next = new Node(e, prev.next); size++; } public void addLast(E e) {
 add(size, e); } public E get(int index) {
 if (index &lt; 0 || index &gt;= size) {
 throw new IllegalArgumentException("Get Failed.Illegal index"); } Node cur = dummyHead.next; for (int i = 0; i &lt; index; i++) {
 cur = cur.next; } return cur.e; } //获取链表的第一个元素 public E getFirst() {
 return get(0); } //获取链表的最后一个元素怒 public E getLast() {
 return get(size - 1); } //修改链表的index元素(0-based)个位置的元素 //不常用的操作 public void set(int index, E e) {
 if (index &lt; 0 || index &gt;= size) {
 throw new IllegalArgumentException("Update Failed.Illegal index"); } else {
 Node cur = dummyHead.next; for (int i = 0; i &lt; index; i++) {
 cur = cur.next; } cur.e = e; } } //查找链表是否存在元素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; } public E remove(int index) {
 if (index &lt; 0 || index &gt;= size) {
 throw new IllegalArgumentException("Update Failed.Illegal index"); } else {
 Node prev = dummyHead; for (int i = 0; i &lt; 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); } @Override public String toString() {
 StringBuilder res = new StringBuilder(); for (Node cur = dummyHead.next; cur != null; cur = cur.next) {
 res.append(cur + "-&gt;"); } res.append("NULL"); return res.toString(); } } </pre></td> 
 </tr> 
 </tbody> 
</table>

#### 测试 ####

![20190504175729.png][]

[20190504172620.png]: /images/20220205/ea7b514e5f04411fa9d4f83d956a5009.png
[20190504172746.png]: /images/20220205/ed6415e6d85c4f739f29c3e0a8a161a1.png
[20190504174653.png]: /images/20220205/447eb328f9504821ad34c0bca62478d7.png
[20190504174905.png]: /images/20220205/d41cd569665b4c329420f1ad6d292c5a.png
[20190504175352.png]: /images/20220205/441c8916347b42ccbbcd3b2d28c2a248.png
[20190504175412.png]: /images/20220205/751cf1b06bab41189b2630ba53cdc0e8.png
[20190504175729.png]: /images/20220205/22972ef5ac70483197726ea9bf4fe664.png