模拟单链表

线性表：
线性表（亦作顺序表）是最基本、最简单、也是最常用的一种数据结构。
线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。
线性表的逻辑结构简单，便于实现和操作。
在实际应用中，线性表都是以栈、队列、字符串等特殊线性表的形式来使用的。
线性结构的基本特征为:
1．集合中必存在唯一的一个“第一元素”；
2．集合中必存在唯一的一个 “最后元素” ；
3．除最后一个元素之外，均有 唯一的后继(后件)；
4．除第一个元素之外，均有 唯一的前驱(前件)。

链表：linked list
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的
每个数据项都被包含在“链结点”（Link）中。
链结点是一个类的对象，这类可叫做Link。链表中有许多类似的链结点，每个Link中都中包含有一个对下一个链结点引用的字段next。
链表对象本身保存了一个指向第一个链结点的引用first。(若没有first，则无法定位)
链表不能像数组那样(利用下标)直接访问到数据项，而需要用数据间的关系来定位，即访问链结点所引用的下一个链结点，而后再下一个，直至访问到需要的数据
在链头插入和删除的时间复杂度为O(1)，因为只需要改变引用的指向即可
而查找、删除指定结点、在指定结点后插入，这些操作都需要平均都需要搜索链表中的一半结点，效率为O(N)。
单链表：
以“结点的序列”表示线性表 称作线性链表（单链表）
是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。(这组存储单元既可以是连续的，也可以是不连续的)
链结点的结构：

存放结点值的数据域data;存放结点的引用 的指针域（链域）next
链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。
每个结点只有一个链域的链表称为单链表（Single Linked List） ， 一个方向, 只有后继结节的引用

/** * 单链表:头插法 后进先出 * 将链表的左边称为链头，右边称为链尾。 * 头插法建单链表是将链表右端看成固定的，链表不断向左延伸而得到的。 * 头插法最先得到的是尾结点 * @author stone */ public class SingleLinkedList<T> { private Link<T> first; //首结点 public SingleLinkedList() { } public boolean isEmpty() { return first == null; } public void insertFirst(T data) {// 插入 到 链头 Link<T> newLink = new Link<T>(data); newLink.next = first; //新结点的next指向上一结点 first = newLink; } public Link<T> deleteFirst() {//删除 链头 Link<T> temp = first; first = first.next; //变更首结点，为下一结点 return temp; } public Link<T> find(T t) { Link<T> find = first; while (find != null) { if (!find.data.equals(t)) { find = find.next; } else { break; } } return find; } public Link<T> delete(T t) { if (isEmpty()) { return null; } else { if (first.data.equals(t)) { Link<T> temp = first; first = first.next; //变更首结点，为下一结点 return temp; } } Link<T> p = first; Link<T> q = first; while (!p.data.equals(t)) { if (p.next == null) {//表示到链尾还没找到 return null; } else { q = p; p = p.next; } } q.next = p.next; return p; } public void displayList() {//遍历 System.out.println("List (first-->last):"); Link<T> current = first; while (current != null) { current.displayLink(); current = current.next; } } public void displayListReverse() {//反序遍历 Link<T> p = first, q = first.next, t; while (q != null) {//指针反向，遍历的数据顺序向后 t = q.next; //no3 if (p == first) {// 当为原来的头时，头的.next应该置空 p.next = null; } q.next = p;// no3 -> no1 pointer reverse p = q; //start is reverse q = t; //no3 start } //上面循环中的if里，把first.next 置空了, 而当q为null不执行循环时，p就为原来的最且一个数据项，反转后把p赋给first first = p; displayList(); } class Link<T> {//链结点 T data; //数据域 Link<T> next; //后继指针，结点 链域 Link(T data) { this.data = data; } void displayLink() { System.out.println("the data is " + data.toString()); } } public static void main(String[] args) { SingleLinkedList<Integer> list = new SingleLinkedList<Integer>(); list.insertFirst(33); list.insertFirst(78); list.insertFirst(24); list.insertFirst(22); list.insertFirst(56); list.displayList(); list.deleteFirst(); list.displayList(); System.out.println("find:" + list.find(56)); System.out.println("find:" + list.find(33)); System.out.println("delete find:" + list.delete(99)); System.out.println("delete find:" + list.delete(24)); list.displayList(); System.out.println("----reverse----"); list.displayListReverse(); } }

打印

List (first-->last): the data is 56 the data is 22 the data is 24 the data is 78 the data is 33 List (first-->last): the data is 22 the data is 24 the data is 78 the data is 33 find:null find:linked_list.SingleLinkedList$Link@4b71bbc9 delete find:null delete find:linked_list.SingleLinkedList$Link@17dfafd1 List (first-->last): the data is 22 the data is 78 the data is 33 ----reverse---- List (first-->last): the data is 33 the data is 78 the data is 22

单链表:尾插法、后进先出——若将链表的左端固定，链表不断向右延伸，这种建立链表的方法称为尾插法。
尾插法建立链表时，头指针固定不动，故必须设立一个尾部的指针，向链表右边延伸，
尾插法最先得到的是头结点。

public class SingleLinkedList2<T> { private Link<T> head; //首结点 public SingleLinkedList2() { } public boolean isEmpty() { return head == null; } public void insertLast(T data) {//在链尾 插入 Link<T> newLink = new Link<T>(data); if (head != null) { Link<T> nextP = head.next; if (nextP == null) { head.next = newLink; } else { Link<T> rear = null; while (nextP != null) { rear = nextP; nextP = nextP.next; } rear.next = newLink; } } else { head = newLink; } } public Link<T> deleteLast() {//删除 链尾 Link<T> p = head; Link<T> q = head; while (p.next != null) {// p的下一个结点不为空，q等于当前的p(即q是上一个，p是下一个) 循环结束时，q等于链尾倒数第二个 q = p; p = p.next; } //delete q.next = null; return p; } public Link<T> find(T t) { Link<T> find = head; while (find != null) { if (!find.data.equals(t)) { find = find.next; } else { break; } } return find; } public Link<T> delete(T t) { if (isEmpty()) { return null; } else { if (head.data.equals(t)) { Link<T> temp = head; head = head.next; //变更首结点，为下一结点 return temp; } } Link<T> p = head; Link<T> q = head; while (!p.data.equals(t)) { if (p.next == null) {//表示到链尾还没找到 return null; } else { q = p; p = p.next; } } q.next = p.next; return p; } public void displayList() {//遍历 System.out.println("List (head-->last):"); Link<T> current = head; while (current != null) { current.displayLink(); current = current.next; } } public void displayListReverse() {//反序遍历 Link<T> p = head, q = head.next, t; while (q != null) {//指针反向，遍历的数据顺序向后 t = q.next; //no3 if (p == head) {// 当为原来的头时，头的.next应该置空 p.next = null; } q.next = p;// no3 -> no1 pointer reverse p = q; //start is reverse q = t; //no3 start } //上面循环中的if里，把head.next 置空了, 而当q为null不执行循环时，p就为原来的最且一个数据项，反转后把p赋给head head = p; displayList(); } class Link<T> {//链结点 T data; //数据域 Link<T> next; //后继指针，结点 链域 Link(T data) { this.data = data; } void displayLink() { System.out.println("the data is " + data.toString()); } } public static void main(String[] args) { SingleLinkedList2<Integer> list = new SingleLinkedList2<Integer>(); list.insertLast(33); list.insertLast(78); list.insertLast(24); list.insertLast(22); list.insertLast(56); list.displayList(); list.deleteLast(); list.displayList(); System.out.println("find:" + list.find(56)); System.out.println("find:" + list.find(33)); System.out.println("delete find:" + list.delete(99)); System.out.println("delete find:" + list.delete(78)); list.displayList(); System.out.println("----reverse----"); list.displayListReverse(); } }

打印

List (head-->last): the data is 33 the data is 78 the data is 24 the data is 22 the data is 56 List (head-->last): the data is 33 the data is 78 the data is 24 the data is 22 find:null find:linked_list.SingleLinkedList2$Link@4b71bbc9 delete find:null delete find:linked_list.SingleLinkedList2$Link@17dfafd1 List (head-->last): the data is 33 the data is 24 the data is 22 ----reverse---- List (head-->last): the data is 22 the data is 24 the data is 33

模拟双端链表，以链表实现栈和队列
双端链表：
双端链表与传统链表非常相似.只是新增了一个属性-即对最后一个链结点的引用rear
这样在链尾插入会变得非常容易，只需改变rear的next为新增的结点即可，而不需要循环搜索到最后一个节点
所以有insertFirst、insertLast
删除链头时，只需要改变引用指向即可；删除链尾时，需要将倒数第二个结点的next置空，
而没有一个引用是指向它的，所以还是需要循环来读取操作

/** * 双端链表 * @author stone */ public class TwoEndpointList<T> { private Link<T> head; //首结点 private Link<T> rear; //尾部指针 public TwoEndpointList() { } public T peekHead() { if (head != null) { return head.data; } return null; } public boolean isEmpty() { return head == null; } public void insertFirst(T data) {// 插入 到 链头 Link<T> newLink = new Link<T>(data); newLink.next = head; //新结点的next指向上一结点 head = newLink; } public void insertLast(T data) {//在链尾 插入 Link<T> newLink = new Link<T>(data); if (head == null) { rear = null; } if (rear != null) { rear.next = newLink; } else { head = newLink; head.next = rear; } rear = newLink; //下次插入时，从rear处插入 } public T deleteHead() {//删除 链头 if (isEmpty()) return null; Link<T> temp = head; head = head.next; //变更首结点，为下一结点 if (head == null) { <span style="white-space:pre"> </span>rear = head; } return temp.data; } public T find(T t) { if (isEmpty()) { return null; } Link<T> find = head; while (find != null) { if (!find.data.equals(t)) { find = find.next; } else { break; } } if (find == null) { return null; } return find.data; } public T delete(T t) { if (isEmpty()) { return null; } else { if (head.data.equals(t)) { Link<T> temp = head; head = head.next; //变更首结点，为下一结点 return temp.data; } } Link<T> p = head; Link<T> q = head; while (!p.data.equals(t)) { if (p.next == null) {//表示到链尾还没找到 return null; } else { q = p; p = p.next; } } q.next = p.next; return p.data; } public void displayList() {//遍历 System.out.println("List (head-->last):"); Link<T> current = head; while (current != null) { current.displayLink(); current = current.next; } } public void displayListReverse() {//反序遍历 if (isEmpty()) { return; } Link<T> p = head, q = head.next, t; while (q != null) {//指针反向，遍历的数据顺序向后 t = q.next; //no3 if (p == head) {// 当为原来的头时，头的.next应该置空 p.next = null; } q.next = p;// no3 -> no1 pointer reverse p = q; //start is reverse q = t; //no3 start } //上面循环中的if里，把head.next 置空了, 而当q为null不执行循环时，p就为原来的最且一个数据项，反转后把p赋给head head = p; displayList(); } class Link<T> {//链结点 T data; //数据域 Link<T> next; //后继指针，结点 链域 Link(T data) { this.data = data; } void displayLink() { System.out.println("the data is " + data.toString()); } } public static void main(String[] args) { TwoEndpointList<Integer> list = new TwoEndpointList<Integer>(); list.insertLast(1); list.insertFirst(2); list.insertLast(3); list.insertFirst(4); list.insertLast(5); list.displayList(); list.deleteHead(); list.displayList(); System.out.println("find:" + list.find(6)); System.out.println("find:" + list.find(3)); System.out.println("delete find:" + list.delete(6)); System.out.println("delete find:" + list.delete(5)); list.displayList(); System.out.println("----reverse----"); list.displayListReverse(); } }

打印

List (head-->last): the data is 4 the data is 2 the data is 1 the data is 3 the data is 5 List (head-->last): the data is 2 the data is 1 the data is 3 the data is 5 find:null find:3 delete find:null delete find:5 List (head-->last): the data is 2 the data is 1 the data is 3 ----reverse---- List (head-->last): the data is 3 the data is 1 the data is 2

使用链表实现栈 ，用前插 单链表就能实现，
本类采用双端链表实现：

public class LinkStack<T> { private TwoEndpointList<T> datas; public LinkStack() { datas = new TwoEndpointList<T>(); } // 入栈 public void push(T data) { datas.insertFirst(data); } // 出栈 public T pop() { return datas.deleteHead(); } // 查看栈顶 public T peek() { return datas.peekHead(); } //栈是否为空 public boolean isEmpty() { return datas.isEmpty(); } public static void main(String[] args) { LinkStack<Integer> stack = new LinkStack<Integer>(); for (int i = 0; i < 5; i++) { stack.push(i); } for (int i = 0; i < 5; i++) { Integer peek = stack.peek(); System.out.println("peek:" + peek); } for (int i = 0; i < 6; i++) { Integer pop = stack.pop(); System.out.println("pop:" + pop); } System.out.println("----"); for (int i = 5; i > 0; i--) { stack.push(i); } for (int i = 5; i > 0; i--) { Integer peek = stack.peek(); System.out.println("peek:" + peek); } for (int i = 5; i > 0; i--) { Integer pop = stack.pop(); System.out.println("pop:" + pop); } } }

打印

peek:4 peek:4 peek:4 peek:4 peek:4 pop:4 pop:3 pop:2 pop:1 pop:0 pop:null ---- peek:1 peek:1 peek:1 peek:1 peek:1 pop:1 pop:2 pop:3 pop:4 pop:5

链表实现 队列 用双端链表实现：

public class LinkQueue<T> { private TwoEndpointList<T> list; public LinkQueue() { list = new TwoEndpointList<T>(); } //插入队尾 public void insert(T data) { list.insertLast(data); } //移除队头 public T remove() { return list.deleteHead(); } //查看队头 public T peek() { return list.peekHead(); } public boolean isEmpty() { return list.isEmpty(); } public static void main(String[] args) { LinkQueue<Integer> queue = new LinkQueue<Integer>(); for (int i = 1; i < 5; i++) { queue.insert(i); } for (int i = 1; i < 5; i++) { Integer peek = queue.peek(); System.out.println("peek:" + peek); } for (int i = 1; i < 5; i++) { Integer remove = queue.remove(); System.out.println("remove:" + remove); } System.out.println("----"); for (int i = 5; i > 0; i--) { queue.insert(i); } for (int i = 5; i > 0; i--) { Integer peek = queue.peek(); System.out.println("peek2:" + peek); } for (int i = 5; i > 0; i--) { Integer remove = queue.remove(); System.out.println("remove:" + remove); } } }

打印

peek:1 peek:1 peek:1 peek:1 remove:1 remove:2 remove:3 remove:4 ---- peek2:5 peek2:5 peek2:5 peek2:5 peek2:5 remove:5 remove:4 remove:3 remove:2 remove:1