建站
咨詢
售后
建站咨詢
新聞中心
[[399074]]
一、前言
在前面兩章我們講解了動態(tài)數(shù)組、棧和隊列的講解，這些底層都是依托靜態(tài)數(shù)組，靠 resize解決固定容量問題的，之前雖然用戶看到的是動態(tài)數(shù)組，但是依然使用的是靜態(tài)數(shù)組，他是依靠 resize 這個方法解決 固定容量問題 ，但是我們今天要講解的 鏈表 不一樣，鏈表是我們數(shù)據(jù)結構學習的一個重點，也有可能是一個難點，為什么鏈表這么重要呢?因為他是最簡單的也是 真正的動態(tài)數(shù)據(jù)結構。
二、為什么鏈表很重要
- 鏈表是一個真正的動態(tài)數(shù)據(jù)結構
- 最簡單的動態(tài)數(shù)據(jù)結構
- 更深入的理解引用(或者指針)
- 更深入的理解遞歸
- 輔助組成其他數(shù)據(jù)結構
更深入的理解引用(或者指針)：和內存相關，雖然在 java 中大家不用手動的管理內存，但是對 鏈表 這種數(shù)據(jù)結構，更加深入的理解，可以幫助大家對引用、指針、甚至計算機系統(tǒng)中和內存管理相關的很多話題，有更加深入的認識。
更深入的理解遞歸：鏈表 本來也是有他非常清晰的遞歸結構的，、由于 鏈表 這種數(shù)據(jù)結構是 數(shù)據(jù)結構，我們可以更加 深入理解遞歸，對于遞歸這種深入理解是不可獲取的。
鏈表 本身也是具有功能性：輔助組成其他數(shù)據(jù)結構(hashMap 、棧和隊列)
三、什么是鏈表
鏈表 是一種數(shù)據(jù)結構，在內存中通過 節(jié)點記錄內存地址 而相互鏈接形成一條鏈的儲存方式。相比數(shù)組而言，鏈表在內存中不需要連續(xù)的區(qū)域，只需要每一個節(jié)點都能夠 記錄下一個節(jié)點 的 內存地址 ，通過 引用 進行查找，這樣的特點也就造就了 鏈表 增刪操作時間消耗很小，而查找遍歷時間消耗很大的特點。
我們日常在 Java 中使用的 LinkedList 即為 雙向鏈表。而在鏈表是由其基本組成單元節(jié)點 (Node) 來實現(xiàn)的。我們在日常中見到的鏈表大部分都是 單鏈表和雙鏈表
單元節(jié)點 (Node)：
- class Node{
- E e;
- Node next;
- }
e 就是鏈表元素
next 指的是當前節(jié)點的下一個節(jié)點
對于 鏈表 來說它就像我們的火車一樣，每一個節(jié)點其實就是一節(jié)車廂，我們在車廂中存儲真正的數(shù)據(jù)，而車廂和車廂之間還要進行連接，讓我們數(shù)據(jù)是整合在一起的，用戶可以方便的在所有的數(shù)據(jù)上進行查詢或其他操作，那么 數(shù)據(jù)和數(shù)據(jù)連接 就是由這個 next 來完成的
當然 鏈表 不能無窮無盡，如果一個節(jié)點的 next 是 Null 了，就說明這個節(jié)點是最后一個節(jié)點了，這就是 鏈表
如下圖所示(單鏈表)：
鏈表的優(yōu)點：真正的動態(tài)，不需要處理固定容量的問題鏈表的缺點：喪失了隨機訪問的能力
在數(shù)組中：每一個索引，直接從數(shù)組中拿出索引對應的元素，這是因為從底層機制上，數(shù)組所開辟的空間，在內存里是連續(xù)分布的，所以我們可以直接可以去找這個數(shù)組的偏移，直接計算出這個數(shù)據(jù)所存儲的內存地址，可以直接使用。
鏈表：而鏈表是靠 Next 一層一層連接的，需要借助這個 Next 一點一點的去找我們需要取出來的元素。
四、創(chuàng)建我們自己的鏈表
4.1 鏈表基本結構
- /**
- * 底層鏈表的內部類
- * @param
- */
- public class LinkedList
{ - //設計私有的內部類，對于用戶來說不需要知道鏈表底層實現(xiàn)，
- // 不需要知道node這個節(jié)點，對用戶屏蔽編碼實現(xiàn)的底層實現(xiàn)
- private class Node{
- public E e;
- public Node next;//public 可以在LinkedList隨意操作
- public Node(E e,Node next){
- this.e = e;
- this.next = next;
- }
- public Node(E e){
- this(e,null);
- }
- public Node(){
- this(null,null);
- }
- @Override
- public String toString() {
- return e.toString();
- }
- }
- }
內部類Node：設計私有的內部類，對于用戶來說不需要知道鏈表底層實現(xiàn)，不需要知道node這個節(jié)點，對用戶屏蔽編碼實現(xiàn)的底層實現(xiàn)e：元素next：指向Node的一個引用
4.2 添加元素
之前我們講的是如何在數(shù)組中添加元素，我們在數(shù)組尾添加元素是非常方便的，因為對于數(shù)組來說是順序排放的，有意思的是對于鏈表來說，恰恰相反，在鏈表頭添加元素是非常方便的，其實這樣非常好理解，對于數(shù)組來說我們有 size 這個變量，它直接指向了數(shù)組中最后一個元素下一個位置，也就是下一個待添加元素的位置，所以直接添加就非常容易，因為有 size 這個變量，在跟蹤數(shù)組的尾巴，而對于鏈表來說我們設立了鏈表的一個頭 head ，而沒有變量來跟蹤鏈表的尾巴,所以我們在鏈表頭添加元素是非常方便的，最關鍵的就是 node.next = head 和 head = node，如下圖所示：
4.2.1 鏈表頭添加元素
代碼實現(xiàn)：
- //在鏈表頭中添加元素e
- public void addFirst(E e){
- //方式一
- // Node node = new Node(e);
- // node.next = head;
- // head = node;
- //方式二
- head = new Node(e,head);
- size ++;
- }
4.2.2 鏈表中間添加元素
我們需要在索引為2的地方添加元素 666，我們只需要找到 元素666要 插入之前的節(jié)點(1) ，我們管它叫 prev，然后把 之前節(jié)點的(1) next 指向 666，然后在將 666的這個 節(jié)點指向之前節(jié)點(1) 的 之后的節(jié)點(2) ，就完成了整個插入了，其中關鍵代碼就是 node.next=prev.next和prev.next=node;，其中關鍵：我們要找到添加節(jié)點的前一個節(jié)點 。
代碼實現(xiàn)：
- //在鏈表的index(0-based)位置添加新的元素e
- public void add(int index,E e){
- if(index < 0 || index > size)
- throw new IllegalArgumentException("Add failed. Illegal index.");
- if(index == 0)
- addFirst(e);
- else{
- Node prev = head;
- for (int i = 0; i < index - 1; i++) {//將prev 放入下一個節(jié)點，直到移動到index - 1
- prev = prev.next;
- //方式一
- // Node node = new Node(e);
- // node.next = prev.next;
- // prev.next = node;
- //方式二
- prev.next = new Node(e,prev.next);
- size++;
- }
- }
- }
- //在鏈表末尾添加新的元素e
- public void addLast(E e){
- add(size,e);
- }
4.2.3 添加操作時間復雜度
4.3 為鏈表設計虛擬頭結點
上面我們介紹了鏈表的添加操作，那么我們在添加的時候遇到了一個問題，就是在鏈表任意一個地方的時候，添加一個元素，在鏈表頭添加一個元素，和在鏈表其他地方添加元素，邏輯上會有差別，為什么在鏈表頭添加元素會比較特殊呢，因為我們在鏈表添加元素的過程，要找到待添加的 之前的一個節(jié)點，但是由于對于鏈表頭沒有之前的一個節(jié)點，不過我們可以自己創(chuàng)建一個頭結點，這個頭節(jié)點就是 虛擬頭結點，這個節(jié)點對于用戶來說是不存在， 用戶也不會感知到這個節(jié)點的存在，我們是屏蔽了這個節(jié)點的存在，如下圖所示：
代碼實現(xiàn)：
- private Node dummyHead;
- int size;
- public LinkedList(){
- dummyHead = new Node(null,null);
- size = 0;
- }
- //獲取鏈表中的元素個數(shù)
- public int getSize(){
- return size;
- }
- //返回鏈表是否為空
- public boolean isEmpty(){
- return size == 0;
- }
- //在鏈表的index(0-based)位置添加新的元素e
- public void add(int index,E e){
- if(index < 0 || index > size)
- throw new IllegalArgumentException("Add failed. Illegal index.");
- Node prev = dummyHead;
- for (int i = 0; i < index; i++)
- prev = prev.next;
- prev.next = new Node(e,prev.next);
- size ++;
- }
- //在鏈表頭中添加元素e
- public void addFirst(E e){
- add(0,e);
- }
- //在鏈表末尾添加新的元素e
- public void addLast(E e){
- add(size,e);
- }
4.4 鏈表元素 get、set、是否存在操作
- //在鏈表的index(0-based)位置添加新的元素e
- public E get(int index){
- if(index < 0 || index > size)
- throw new IllegalArgumentException("Get failed. Illegal index.");
- Node cur = dummyHead.next;
- for (int i = 0; i < index; i++)
- cur = cur.next;
- return cur.e;
- }
- //獲得鏈表的第一個元素
- public E getFirst(){
- return get(0);
- }
- //獲取鏈表的最后一個元素
- public E getLast(){
- return get(size - 1);
- }
- //在鏈表的index(0-based)位置添加新的元素e
- public void set(int index,E e){
- if(index < 0 || index > size)
- throw new IllegalArgumentException("Set failed. Illegal index.");
- Node cur = dummyHead.next;
- for (int i = 0; i < index; i++)
- cur = cur.next;
- cur.e = e;
- }
- //查找鏈表中是否有元素e
- public boolean contains(E e){
- Node cur = dummyHead.next;
- while (cur != null){
- if(cur.e.equals(e))
- return true;
- cur = cur.next;
- }
- return false;
- }
4.5.1 修改和查找操作時間復雜度
4.5 刪除鏈表元素
加入我們想要刪除索引為 (2) 位置的元素，我們需要找到 待刪除節(jié)點之前的一個位置，也就是(1) ，我們用 prev 表示，找到這個節(jié)點之后，那么 (2) 就是我們需要刪除的索引了 我們叫 delNode，如下圖所示：
代碼實現(xiàn)：
- //從鏈表中刪除Index(0-based)位置的元素，返回刪除的元素
- public E remove(int index){
- if(index < 0 || index > size)
- throw new IllegalArgumentException("Remove failed. Illegal index.");
- Node prev = dummyHead;
- for (int i = 0; i < index; i++)
- prev = prev.next;
- Node retNode = prev.next;
- prev.next = retNode.next;
- retNode.next = null;
- size --;
- return retNode.e;
- }
- //從鏈表中刪除第一個位置的元素
- public E removeFirst(){
- return remove(0);
- }
- //從鏈表中刪除最后一個位置的元素
- public E removeLast(){
- return remove(size - 1);
- }
4.5.1 刪除操作時間復雜度
4.6 完整代碼
- /**
- * 底層鏈表的內部類
- * @param
- */
- public class LinkedList
{ - private class Node{
- public E e;
- public Node next;//public 可以在LinkedList隨意操作
- public Node(E e,Node next){
- this.e = e;
- this.next = next;
- }
- public Node(E e){
- this(e,null);
- }
- public Node(){
- this(null,null);
- }
- @Override
- public String toString() {
- return e.toString();
- }
- }
- private Node dummyHead;
- int size;
- public LinkedList(){
- dummyHead = new Node(null,null);
- size = 0;
- }
- //獲取鏈表中的元素個數(shù)
- public int getSize(){
- return size;
- }
- //返回鏈表是否為空
- public boolean isEmpty(){
- return size == 0;
- }
- //在鏈表頭中添加元素e
- public void addFirst(E e){
- //方式一
- // Node node = new Node(e);
- // node.next = head;
- // head = node;
- //方式二
- add(0,e);
- }
- //在鏈表的index(0-based)位置添加新的元素e
- public void add(int index,E e){
- if(index < 0 || index > size)
- throw new IllegalArgumentException("Add failed. Illegal index.");
- Node prev = dummyHead;
- for (int i = 0; i < index; i++)
- prev = prev.next;
- prev.next = new Node(e,prev.next);
- size ++;
- }
- //在鏈表末尾添加新的元素e
- public void addLast(E e){
- add(size,e);
- }
- //在鏈表的index(0-based)位置添加新的元素e
- public E get(int index){
- if(index < 0 || index > size)
- throw new IllegalArgumentException("Get failed. Illegal index.");
- Node cur = dummyHead.next;
- for (int i = 0; i < index; i++)
- cur = cur.next;
- return cur.e;
- }
- //獲得鏈表的第一個元素
- public E getFirst(){
- return get(0);
- }
- //獲取鏈表的最后一個元素
- public E getLast(){
- return get(size - 1);
- }
- //在鏈表的index(0-based)位置添加新的元素e
- public void set(int index,E e){
- if(index < 0 || index > size)
- throw new IllegalArgumentException("Set failed. Illegal index.");
- Node cur = dummyHead.next;
- for (int i = 0; i < index; i++)
- cur = cur.next;
- cur.e = e;
- }
- //查找鏈表中是否有元素e
- public boolean contains(E e){
- Node cur = dummyHead.next;
- while (cur != null){
- if(cur.e.equals(e))
- return true;
- cur = cur.next;
- }
- return false;
- }
- //從鏈表中刪除Index(0-based)位置的元素，返回刪除的元素
- public E remove(int index){
- if(index < 0 || index > size)
- throw new IllegalArgumentException("Remove failed. Illegal index.");
- Node prev = dummyHead;
- for (int i = 0; i < index; i++)
- prev = prev.next;
- Node retNode = prev.next;
- prev.next = retNode.next;
- retNode.next = null;
- size --;
- return retNode.e;
- }
- //從鏈表中刪除第一個位置的元素
- public E removeFirst(){
- return remove(0);
- }
- //從鏈表中刪除最后一個位置的元素
- public E removeLast(){
- return remove(size - 1);
- }
- @Override
- public String toString() {
- StringBuilder res = new StringBuilder();
- for (Node cur = dummyHead.next;cur != null; cur= cur.next)
- res.append(cur + "->");
- res.append("Null");
- return res.toString();
- }
- }
4.2.7 結果測試：
- public static void main(String[] args) {
- LinkedList
linkedList = new LinkedList<>(); - //添加元素 0-4
- for (int i = 0; i < 5 ; i++) {
- linkedList.addFirst(i);
- System.out.println(linkedList);
- }
- //添加第二個元素添加 666
- linkedList.add(2,666);
- System.out.println(linkedList);
- //刪除第二個元素 666
- linkedList.remove(2);
- System.out.println(linkedList);
- //刪除第一個元素
- linkedList.removeFirst();
- System.out.println(linkedList);
- //刪除最后一個元素
- linkedList.removeLast();
- System.out.println(linkedList);
- }
打印結果：
- 0->Null
- 1->0->Null
- 2->1->0->Null
- 3->2->1->0->Null
- 4->3->2->1->0->Null
- 4->3->666->2->1->0->Null
- 4->3->2->1->0->Null
- 3->2->1->0->Null
- 3->2->1->Null
四、鏈表時間復雜度分析
對于增加和刪除來說，如果是對鏈表頭進行操作，那么就是 O(1) 級別的復雜度，對于查詢來說，也是一樣
五、鏈表應用
5.1 使用棧實現(xiàn)鏈表
5.1.1 接口類：
- /**
- * @program: Data-Structures
- * @ClassName Stack
- * @description:
- * @author: lyy
- * @create: 2019-11-20 21:51
- * @Version 1.0
- **/
- public interface Stack
{ - int getSize();
- boolean isEmpty();
- void push(E e);
- E pop();
- E peek();
- }
5.1.2 實現(xiàn)類：
- import com.lyy.datasty.Mystack.Stack;
- //鏈表棧實現(xiàn)
- public class LinkedListStack
implements Stack { - private LinkedList1
list; - public LinkedListStack(){
- list = new LinkedList1<>();
- }
- @Override
- public int getSize() {
- return list.getSize();
- }
- @Override
- public boolean isEmpty() {
- return list.isEmpty();
- }
- @Override
- public void push(E e) {
- list.addFirst(e);
- }
- @Override
- public E pop() {
- return list.removeFirst();
- }
- @Override
- public E peek() {
- return list.getFirst();
- }
- @Override
- public String toString() {
- StringBuilder res = new StringBuilder();
- res.append("Stack：top ");
- res.append(list);
- return res.toString();
- }
- }
5.1.3 運行結果：
- public static void main(String[] args) {
- LinkedListStack
stack = new LinkedListStack<>(); - for (int i = 0; i < 5; i++) {
- stack.push(i);
- System.out.println(stack);
- }
- stack.pop();
- System.out.println(stack);
- }
5.1.4 結果打?。?/h3>
- Stack：top 0->Null
- Stack：top 1->0->Null
- Stack：top 2->1->0->Null
- Stack：top 3->2->1->0->Null
- Stack：top 4->3->2->1->0->Null
- Stack：top 3->2->1->0->Null
5.2 使用鏈表實現(xiàn)隊列
5.2.1 接口類
- /**
- * @program: Data-Structures
- * @ClassName Queue
- * @description:
- * @author: lyy
- * @create: 2019-11-21 21:54
- * @Version 1.0
- **/
- public interface Queue
{
-
- int getSize();
- boolean isEmpty();
- void enqueue(E e);
- E dequeue();
- E getFront();
-
-
- }
5.2.2 實現(xiàn)類
- public class LinkedListQueue
implements Queue{
-
- //設計私有的內部類，對于用戶來說不需要知道鏈表底層實現(xiàn)，
- // 不需要知道node這個節(jié)點，對用戶屏蔽編碼實現(xiàn)的底層實現(xiàn)
- private class Node{
- public E e;
- public Node next;//public 可以在LinkedList隨意操作
-
- public Node(E e, Node next){
- this.e = e;
- this.next = next;
- }
-
- public Node(E e){
- this(e,null);
- }
-
- public Node(){
- this(null,null);
- }
-
- @Override
- public String toString() {
- return e.toString();
- }
- }
-
- private Node head,tail;
- private int size;
-
- public LinkedListQueue(){
- head = null;
- tail = null;
- size = 0;
- }
-
-
- @Override
- public int getSize() {
- return&nb
文章題目：數(shù)據(jù)結構線性結構篇—鏈表
網頁鏈接：http://www.5511xx.com/article/djhcedo.html
- Stack：top 0->Null
- Stack：top 1->0->Null
- Stack：top 2->1->0->Null
- Stack：top 3->2->1->0->Null
- Stack：top 4->3->2->1->0->Null
- Stack：top 3->2->1->0->Null
- /**
- * @program: Data-Structures
- * @ClassName Queue
- * @description:
- * @author: lyy
- * @create: 2019-11-21 21:54
- * @Version 1.0
- **/
- public interface Queue
{ - int getSize();
- boolean isEmpty();
- void enqueue(E e);
- E dequeue();
- E getFront();
- }
- public class LinkedListQueue
implements Queue { - //設計私有的內部類，對于用戶來說不需要知道鏈表底層實現(xiàn)，
- // 不需要知道node這個節(jié)點，對用戶屏蔽編碼實現(xiàn)的底層實現(xiàn)
- private class Node{
- public E e;
- public Node next;//public 可以在LinkedList隨意操作
- public Node(E e, Node next){
- this.e = e;
- this.next = next;
- }
- public Node(E e){
- this(e,null);
- }
- public Node(){
- this(null,null);
- }
- @Override
- public String toString() {
- return e.toString();
- }
- }
- private Node head,tail;
- private int size;
- public LinkedListQueue(){
- head = null;
- tail = null;
- size = 0;
- }
- @Override
- public int getSize() {
- return&nb
文章題目：數(shù)據(jù)結構線性結構篇—鏈表
網頁鏈接：http://www.5511xx.com/article/djhcedo.html
