模擬單鏈表
線性表：
線性表（亦作順序表）是最基本、最簡單、也是最常用的一種數據結構。
線性表中數據元素之間的關系是一對一的關系，即除了第一個和最后一個數據元素之外，其它數據元素都是首尾相接的。
線性表的邏輯結構簡單，便于實現和操作。
在實際應用中，線性表都是以棧、隊列、字符串等特殊線性表的形式來使用的。
線性結構的基本特征為:
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
新聞熱點
疑難解答
