Java数据结构：利用Sentinel实现链接列表/LinkedList，并用搜索、插入与删除来测试它（第九周）

Java数据结构：利用Sentinel实现链接列表/LinkedList，并用搜索、插入与删除来测试它（第九周）

题目来源：大工慕课 链接
作者：Caleb Sung

链接列表/链表

数据的存储一般分线性存储结构和链式存储结构两种。前者是一种顺序的存储方式，在内存中用一块连续的内存空间存储数据，即逻辑上相连的物理位置相邻，比较常见的就是数组；后者是一种链式存储方式，不保证顺序性，逻辑上相邻的元素之间用指针所指定，它不是用一块连续的内存存储，逻辑上相连的物理位置不一定相邻。
链表是一种递归的数据结构，它要么为空（null），要么指向是指向一个结点（node）的引用，该节点含有一个泛型元素（该泛型元素可以是任意数据类型），和一个指向另一个链表的引用。链表有很多种，下面主要介绍单向链表、双端链表、有序链表、双向链表。

单向链表

单向链表是最简单、最基础的链表，它的一个结点（node）分两部分，第一部分存储结点的数据信息（data），第二部分存储指向下一结点的地址（next）信息。最后一个结点（链尾）指向一个空地址（null）。单向链表一般只在链表表头（链头）结点的位置插入元素，这样每次新加入的元素都会在链头位置，而最先加入的元素会在链尾位置。删除操作时，如果在链头位置删除，只需要把头结点指向其下一个结点即可；如果是在中间位置删除，只需要将其前一个结点指向其下一个结点即可。

双端链表

双端链表和单向链表大体上是一样的，不同的是，单向链表在表尾部分插入元素时，需要从头结点一直遍历到尾结点才能进行插入操作，这样难免有些繁琐。因此如果加入一个对尾结点的引用，这样就可以很方便地在尾结点进行插入操作，这就是双端链表。除了有一个头结点（head），还有一个尾结点（tail）。注意它和后面双向链表的区别！

双向链表/循环链表

前面的几种链表只能从头结点遍历到尾结点这一个方向，每个结点都只能指向其下一个结点。而双向链表的每个结点既能指向下一个结点，又能指向前一个结点，双向链表既能从头结点向尾结点遍历，又能从尾结点向头结点遍历，既有一个头结点，又有一个尾结点。

参考代码

接下来的代码用来实现前文介绍中的最后一种链表，也即双向链表或者循环链表。按照题目要求，还对这个链表进行了测试。

public class test {public static void main(String[] args) {// TODO Auto-generated method stubLinkedList ll = new LinkedList();System.out.println("The LinkedList is:");for (int i = 1; i < 11; i++)ll.insert(i);ll.print();System.out.println("Insert -1 Test :");ll.insert(-1);ll.print();System.out.println("Delete 5 Test :");ll.delete(5);ll.print();System.out.println("Delete 10 Test :");ll.delete(10);ll.print();}}class Node {public Node prev;public Node next;public int key;public Node(int key) {this.key = key;prev = null;next = null;}
}class LinkedList {private Node sentinel;public LinkedList() {sentinel = new Node(Integer.MIN_VALUE); = sentinel;sentinel.prev = sentinel;}public void insert(Node x) {x.next = ;prev =  = x;x.prev = sentinel;}public void insert(int key) {Node i = new Node(key);insert(i);}public void delete(Node x) { = x.prev = x.prev;}public void delete(int key) {delete(search(key));}// search外部接口public Node search(int key) {return , key);}// search实体private Node search(Node i, int key) {if (i.key == key)return i;else if (i == sentinel)return i;i = i.next;return search(i, key);}public void print() {Node i = ;while (i != sentinel) {System.out.print(i.key + " ");i = i.next;}System.out.println();}
}

运行效果

The LinkedList is:
10 9 8 7 6 5 4 3 2 1 
Insert -1 Test :
-1 10 9 8 7 6 5 4 3 2 1 
Delete 5 Test :
-1 10 9 8 7 6 4 3 2 1 
Delete 10 Test :
-1 9 8 7 6 4 3 2 1