【从今天开始好好学数据结构03】链表

 

今天我们来聊聊“链表（Linked list）”这个数据结构。

在我们上一章中【从今天开始好好学数据结构02】栈与队列栈与队列底层都是采用顺序存储的这种方式的，而今天要聊的链表则是采用链式存储，链表可以说是继数组之后第二种使用得最广泛的通用数据结构了,可见其重要性！

相比数组，链表是一种稍微复杂一点的数据结构。对于初学者来说，掌握起来也要比数组稍难一些。这两个非常基础、非常常用的数据结构，我们常常将会放到一块儿来比较。所以我们先来看，这两者有什么区别。数组需要一块连续的内存空间来存储，对内存的要求比较高。而链表恰恰相反，它并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用,链表结构五花八门，今天我重点给你介绍三种最常见的链表结构，它们分别是：单链表、双向链表和循环链表。

链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址NULL，表示这是链表上最后一个结点。

@

单链表

package demo2;  //一个节点 public class Node {      //节点内容     int data;     //下一个节点     Node next;          public Node(int data) {         this.data=data;     }          //为节点追回节点     public Node append(Node node) {         //当前节点         Node currentNode = this;         //循环向后找         while(true) {             //取出下一个节点             Node nextNode = currentNode.next;             //如果下一个节点为null,当前节点已经是最后一个节点             if(nextNode==null) {                 break;             }             //赋给当前节点             currentNode = nextNode;         }         //把需要追回的节点追加为找到的当前节点的下一个节点         currentNode.next=node;         return this;     }          //插入一个节点做为当前节点的下一个节点     public void after(Node node) {         //取出下一个节点，作为下下一个节点         Node nextNext = next;         //把新节点作为当前节点的下一个节点         this.next=node;         //把下下一个节点设置为新节点的下一个节点         node.next=nextNext;     }          //显示所有节点信息     public void show() {         Node currentNode = this;         while(true) {             System.out.print(currentNode.data+" ");             //取出下一个节点             currentNode=currentNode.next;             //如果是最后一个节点             if(currentNode==null) {                 break;             }         }         System.out.println();     }          //删除下一个节点     public void removeNext() {         //取出下下一个节点         Node newNext = next.next;         //把下下一个节点设置为当前节点的下一个节点。         this.next=newNext;     }          //获取下一个节点     public Node next() {         return this.next;     }          //获取节点中的数据     public int getData() {         return this.data;     }          //当前节点是否是最后一个节点     public boolean isLast() {         return next==null;     }      } 

单链表测试类

package demo2.test;  import demo2.Node;