1.鏈表的概念及結構

鏈表是一種物理存儲結構上非連續存儲結構，數據元素的邏輯順序是通過鏈表中的引用鏈接次序實現的 。 可以形象的理解，在邏輯上來看，鏈表就像是一節節火車車廂。

鏈表的分類：鏈表的結構有很多種，單向或雙向、帶頭或不帶頭、循環或不循環。這篇文章就從最簡單的鏈表結構講起———不帶頭單向非循環鏈表(單鏈表)。

2.單鏈表模擬實現

為了更好的學習對于單鏈表的操作。我們自己模擬實現一些基本的功能。

1.準備工作

接口

package List;public interface IList {//頭插法void addFirst(int data);//尾插法public void addLast(int data);//任意位置插入,第一個數據節點為0號下標public void addIndex(int index,int data);//查找是否包含關鍵字key是否在單鏈表當中public boolean contains(int key);//刪除第一次出現關鍵字為key的節點public void remove(int key);//刪除所有值為key的節點public void removeAllKey(int key);//得到單鏈表的長度public int size();//清空public void clear() ;//打印public void display() ;
}

通過實現接口中的抽象方法實現單鏈表增刪查改的實現。

單鏈表的定義

單鏈表(SinglyLinkedList)的定義需要定義單個節點ListNode。單個節點有data存儲數據，next存儲下一個節點的引用。同時單鏈表還需要一個成員變量head存儲單鏈表的頭位置。基于以上的需要可以把ListNode定義為單鏈表的內部類。

public class SinglyLinkedList {public class ListNode{public int data;public ListNode next;public ListNode(int data) {this.data = data;}}public ListNode head;
}

2.具體接口實現

添加

頭插

@Overridepublic void addFirst(int data) {ListNode newnode = new ListNode(data);newnode.next = head;head = newnode;}

尾插

@Overridepublic void addLast(int data) {ListNode newnode = new ListNode(data);//鏈表為空if(head == null){head = newnode;return;}//鏈表不為空，找尾尾插ListNode cur = head;while (cur.next != null){cur = cur.next;}cur.next = newnode;}

在index位置插入

private void CheckIndex(int index){int len = this.size();if(index < 0 || index > len){throw new IllegalIndexException("index不合法");}}@Overridepublic void addIndex(int index, int data) {try {CheckIndex(index);ListNode newnode = new ListNode(data);if(index == 0){addFirst(data);}if(index == size()){addLast(data);}ListNode cur = head;while(index - 1 != 0){cur = cur.next;index--;}newnode.next = cur.next;cur.next = newnode;}catch (IllegalIndexException e){e.printStackTrace();}}

?刪除

刪除找到第一個key值

@Overridepublic void remove(int key) {if(head == null){return;}//解決頭節點問題if(head.data == key){head = head.next;return;}ListNode cur = head;while(cur.next.data != key){cur = cur.next;}ListNode del = cur.next;cur.next = del.next;}

刪除所有等于key的值

@Overridepublic void removeAllKey(int key) {if(head == null){return;}ListNode prev = head;ListNode cur = head.next;while (cur != null){if(cur.data == key){prev.next = cur.next;}else {prev = cur;}cur = cur.next;}//解決頭節點data等于key的情況if(head.data == key){head = head.next;}}

查找

@Overridepublic boolean contains(int key) {ListNode cur = head;while (cur != null){if(cur.data == key){return true;}cur = cur.next;}return false;}

得到size

@Overridepublic int size() {int count = 0;ListNode cur = head;while(cur != null){count++;cur = cur.next;}return count ;}

清空

@Overridepublic void clear() {ListNode cur = head;while(cur != null){ListNode ret = cur;cur.next = null;cur = ret.next;}head = null;}

打印

@Overridepublic void display() {ListNode cur = this.head;while(cur != null){System.out.print(cur.data + " ");cur = cur.next;}System.out.println();}

2.鏈表oj

看這篇文章：單鏈表oj練習(C語言版)

雖然是C語言完成的，但是做題的思想是一樣的。

3.LinkedList的模擬實現

LinkedList是java標準庫提供的雙向鏈表的實現。還是一樣為了更好的理解并運用，先自己模擬實現一個。

1.準備工作

接口

接口和上面的單鏈表接口一樣。

MyLinkedList的定義

和上面的單鏈表不同的是ListNode里多一個prev用于存儲上一個節點的引用和MyLinkedList多一個成員last存儲雙向鏈表的尾。

2.具體接口實現

添加

@Overridepublic void addFirst(int data) {ListNode newnode = new ListNode(data);if(head == null){head = last = newnode;}else {newnode.next = head;head.prev = newnode;head = newnode;}}@Overridepublic void addLast(int data) {ListNode newnode = new ListNode(data);if(head == null){head = last = newnode;}else {last.next = newnode;newnode.prev = last;last = newnode;}}private void CheckIndex(int index){if(index < 0 || index > size()){throw new IllegalIndexException("index位置不合法");}}private ListNode FindIndexnode(int index){ListNode cur = head;while(index-1 > 0){cur = cur.next;index--;}return cur;}@Overridepublic void addIndex(int index, int data) {try {CheckIndex(index);if(index == 0){addFirst(data);}if(index == size()){addLast(data);}ListNode newnode = new ListNode(data);ListNode cur = FindIndexnode(index);newnode.next = cur;cur.prev.next = newnode;newnode.prev = cur.prev;newnode.next = cur;}catch(IllegalIndexException e){e.printStackTrace();}}

刪除

@Overridepublic void remove(int key) {ListNode cur = head;while(cur != null){if(cur.data == key){if(cur == head){head = head.next;if(head != null){head.prev = null;}}else {cur.prev.next = cur.next;if (cur.next == null) {last = last.prev;} else {cur.next.prev = cur.prev;}}return;}cur = cur.next;}}@Overridepublic void removeAllKey(int key) {ListNode cur = head;while(cur != null){if(cur.data == key){if(cur == head){head = head.next;if(head != null){head.prev = null;}}else {cur.prev.next = cur.next;if (cur.next == null) {last = last.prev;} else {cur.next.prev = cur.prev;}}}cur = cur.next;}}

查找 打印 得到size

和單鏈表一樣，本質都是遍歷鏈表

清空

@Overridepublic void clear() {ListNode cur = head;while(cur != null){ListNode Curn = cur.next;cur.prev = null;cur.next = null;cur = Curn;}head = last = head;}

4.LinkedList的使用?

1.構造

public static void main(String[] args) {// 構造一個空的LinkedListList<Integer> list1 = new LinkedList<>();List<String> list2 = new java.util.ArrayList<>();list2.add("JavaSE");list2.add("JavaWeb");list2.add("JavaEE");// 使用ArrayList構造LinkedListList<String> list3 = new LinkedList<>(list2);
}

2.其他方法?

?

?