0. 序列

之前有一篇文章講解了“動(dòng)態(tài)數(shù)組”，以及通過這個(gè)“動(dòng)態(tài)數(shù)組”實(shí)現(xiàn)了棧和隊(duì)列，而這里的“動(dòng)態(tài)數(shù)組”的底層其實(shí)依靠的是靜態(tài)數(shù)組，只是靠resize解決固定容量的問題。而今天所要講解的“鏈表”數(shù)據(jù)結(jié)構(gòu)，它是真正的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)。

鏈表也屬于線性表（不了解線性表概念的，可點(diǎn)擊跳轉(zhuǎn)閱讀http://www.itdecent.cn/p/efa6a9d3a975），由于其在內(nèi)存中的空間分配是不連續(xù)的，所以它是動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)。

這篇文章我們講解鏈表的添加、查詢、遍歷、刪除操作。

1. 簡介

鏈表簡介

① 鏈表將數(shù)據(jù)存儲(chǔ)在“節(jié)點(diǎn)”（Node）中
② e 就是我們存放數(shù)據(jù)的類型，next 相當(dāng)于一個(gè)指針，指向下一個(gè)存儲(chǔ)數(shù)據(jù)的節(jié)點(diǎn)
③ 節(jié)點(diǎn)的next 指針指向null，表明這是最后一個(gè)節(jié)點(diǎn)。

2. 特點(diǎn)

• 優(yōu)點(diǎn)：
  ① 插入和刪除數(shù)據(jù)相當(dāng)方便，不需要移動(dòng)大量數(shù)據(jù)。
  ② 內(nèi)存分配發(fā)生在運(yùn)行時(shí)期，不需要事先聲明可能占用的最大的內(nèi)存空間，能夠充分節(jié)省內(nèi)存。
• 缺點(diǎn)：
  ① 設(shè)計(jì)時(shí)較為麻煩。
  ② 查找和修改數(shù)據(jù)必須按順序找到數(shù)據(jù)為止，即喪失了隨機(jī)訪問的能力。

3. 數(shù)組和鏈表的對(duì)比

• 數(shù)組
  • 數(shù)組最好用于索引有語意的情況。
  • 最大的優(yōu)點(diǎn)：支持快速查詢修改
• 鏈表
  • 鏈表不適合用于索引有語意的情況
  • 最大的優(yōu)點(diǎn)：支持快速插入和刪除

4. 定義一個(gè)鏈表的節(jié)點(diǎn)

public class LinkedList<E> {

    private class Node {
        public E e;
        public Node next;

        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; // 1. 指向第一個(gè)節(jié)點(diǎn)
    private int size; // 2. 記錄元素個(gè)數(shù)

    public int getSize() {
        return size;
    }

    // 3. 初始化鏈表的時(shí)候 鏈表的頭部為null
    public LinkedList() {
        head = null;
        size = 0;
    }

    // 4. 返回鏈表是否為空
    public boolean isEmpty() {
        return size == 0;
    }
}

① 代碼 1 ：定義變量head，指向第一個(gè)Node節(jié)點(diǎn)
② 代碼 2 ：記錄元素的個(gè)數(shù)
③ 代碼 3 ：初始化鏈表的時(shí)候，鏈表元素?cái)?shù)量為0，頭部節(jié)點(diǎn)指向null。
④ 代碼 4 ：當(dāng)元素的個(gè)數(shù)為0的時(shí)候，證明鏈表是空的。

5. 添加元素

• 在鏈表頭添加新的元素e
  如果是數(shù)組，向尾部添加元素比較方便，因?yàn)槭庆o態(tài)的數(shù)據(jù)結(jié)構(gòu)，在內(nèi)存中的空間分配是連續(xù)的，記錄下size，即tail == size，tail指向的位置就是下一個(gè)為數(shù)組開辟的空間。
  如果是鏈表，因?yàn)槲覀冎烙肋h(yuǎn)知道第一個(gè)元素的位置，即head指針?biāo)赶虻膬?nèi)存空間。所以鏈表向首部添加元素比較方便，只需要讓需要添加的元素的next指針指向原來的第一個(gè)元素節(jié)點(diǎn)，然后移動(dòng)下head指針的指向就可以了，如圖所示：

  
  
  鏈表首部添加元素

    public void addFirst(E e){
        /**
         *         Node node = new Node(e);
         *         node.next = head;
         *         head = node;
         */
        head = new Node(e,head); // 代碼1
        size ++;
    }

代碼1相當(dāng)于注釋中的兩句話，無非是把元素e傳入，并且把next指針指向下一個(gè)節(jié)點(diǎn)，然后再把這個(gè)head指針指向新添加的Node節(jié)點(diǎn)。

• 在鏈表中間添加元素

  
  
  添加元素到鏈表中間位置
  
  

  既然節(jié)點(diǎn)之間的鏈接是通過指針next來鏈接的，那如果我想添加節(jié)點(diǎn)數(shù)據(jù)為666的數(shù)據(jù)到節(jié)點(diǎn)數(shù)據(jù)為1和2的節(jié)點(diǎn)中間的位置，那么我只需要找到要添加的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)。我們指定這個(gè)節(jié)點(diǎn)是prev。此時(shí)，我們讓想插入的節(jié)點(diǎn)的指針next指向prev節(jié)點(diǎn)指向的節(jié)點(diǎn)，然后讓prev節(jié)點(diǎn)的指針next指向新添加的節(jié)點(diǎn)即可。

    // 在鏈表的index位置添加新的元素e
    // 在鏈表中不是一個(gè)常用的操作，練習(xí)用：
    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 = prev.next;

//            Node node = new Node(e);
//            node.next = prev.next;
//            prev.next = node;
            prev.next = new Node(e, prev.next);
            size++;
        }
    }

① 引入了一個(gè)概念索引index，假設(shè)我們把第一個(gè)節(jié)點(diǎn)當(dāng)做索引0，最后一個(gè)節(jié)點(diǎn)當(dāng)作索引size -1 ，這樣插入的時(shí)候就能和數(shù)組一樣，插入到我們想要插入的位置。
② 這里首先判斷index的合法性，最小0，最大size，然后判斷下當(dāng)index == 0 的時(shí)候調(diào)用addFirst方法即可，插入到鏈表中間和末尾的時(shí)候就可以執(zhí)行下面的邏輯：找到要插入的位置的前一個(gè)節(jié)點(diǎn)prev即可。

• 向鏈表末尾添加元素

    // 在鏈表末尾添加新的元素e
    public void addLast(E e) {
        add(size, e);
    }

6. 設(shè)立虛擬頭節(jié)點(diǎn)

在上一小節(jié)我們發(fā)現(xiàn)，當(dāng)插入元素的位置為0的時(shí)候，我們需要進(jìn)行特殊處理，因?yàn)槲覀兲砑釉氐姆椒ㄊ钦业揭砑釉氐奈恢玫那耙粋€(gè)節(jié)點(diǎn)prev，而索引為0的節(jié)點(diǎn)并沒有前一個(gè)節(jié)點(diǎn)，所以這里我們?yōu)殒湵碓O(shè)立一個(gè)虛擬頭節(jié)點(diǎn)。

虛擬頭節(jié)點(diǎn)

我們把這個(gè)虛擬頭節(jié)點(diǎn)稱為dummyHead，它存儲(chǔ)的元素是null，對(duì)調(diào)用者來說是沒有意義的，但是對(duì)邏輯非常有意義，和循環(huán)隊(duì)列浪費(fèi)一個(gè)空間的設(shè)計(jì)意義相同。下面我們修改下相關(guān)代碼：

public class LinkedList<E> {

    private class Node {
        public E e;
        public Node next;

        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; // 1. 指向第一個(gè)節(jié)點(diǎn)
    private int size; // 2. 記錄元素個(gè)數(shù)

    public int getSize() {
        return size;
    }

    // 3. 初始化鏈表的時(shí)候 鏈表的頭部為null
    public LinkedList() {
        dummyHead = new Node(); // 5.鏈表初始化
        size = 0;
    }

    // 4. 返回鏈表是否為空
    public boolean isEmpty() {
        return size == 0;
    }

    // 在鏈表的index位置添加新的元素e
    // 在鏈表中不是一個(gè)常用的操作，練習(xí)用：
    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++) // 6. 前面添加了一個(gè)虛擬頭節(jié)點(diǎn)，這里index-1 修改為index，即多執(zhí)行一個(gè)循環(huán)
            prev = prev.next;
        
        prev.next = new Node(e, prev.next);
        size++;
    }

    // 在鏈表頭添加新的元素e
    public void addFirst(E e) {
        add(0, e); // 7. 在鏈表頭添加元素不用單獨(dú)處理，調(diào)用add方法即可
    }

    // 在鏈表末尾添加新的元素e
    public void addLast(E e) {
        add(size, e);
    }
}

① 代碼1：現(xiàn)在的head節(jié)點(diǎn)，為虛擬頭節(jié)點(diǎn)dummyHead
② 代碼5：鏈表初始化的時(shí)候，虛擬頭節(jié)點(diǎn)其存儲(chǔ)的元素為null，指針next指向null
③ 代碼6：由于我們?cè)阪湵淼念^添加了一個(gè)虛擬頭節(jié)點(diǎn)，所以當(dāng)我們遍歷的時(shí)候，需要多執(zhí)行一次循環(huán)，才能找到prev節(jié)點(diǎn)
④ 代碼7：由于添加了虛擬頭節(jié)點(diǎn)，我們就不用額外的處理當(dāng)索引為0的時(shí)候，而是可以復(fù)用add方法。

7. 鏈表的遍歷、查詢和修改

• 查詢

    // 查詢
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Add failed. Illegal index.");
        }
        
        Node cur = dummyHead.next;
        for (int i = 0; i < index ; i++) {
            cur = cur.next;
        }
        return  cur.e;
    }

① 首先對(duì)index索引進(jìn)行校驗(yàn)，在校驗(yàn)之前我們要明白一件事情：在鏈表初始化的時(shí)候會(huì)創(chuàng)建一個(gè)虛擬頭節(jié)點(diǎn)，而這個(gè)節(jié)點(diǎn)并不會(huì)導(dǎo)致size++，只有add了有意義的元素，才會(huì)導(dǎo)致size++。假設(shè)添加了a、b、c、d、e五個(gè)元素，size == 5，而最大索引index == 4，所以這里index不能等于size。
② 現(xiàn)在鏈表中的元素分別是a、b、c、d、e五個(gè)元素，當(dāng)index == 4 的時(shí)候，我們只需要遍歷4次，即從索引0開始遍歷，到索引3即可，就能找到索引為index為4的位置的節(jié)點(diǎn)cur。如下圖：

查詢.jpg

• 查詢第一個(gè)和最后一個(gè)元素：

    // 查詢第一個(gè)元素
    public E getFirst(){
        return get(0);
    }
    
    // 查詢最后一個(gè)元素
    public E getLast(){
        return get(size - 1);
    }

• 修改元素：

    // 修改
    public void set(int index, E e) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Add failed. Illegal index.");
        }

        Node cur = dummyHead.next;
        for (int i = 0; i < index; i++)
            cur = cur.next;
        cur.e = 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;
    }

• 遍歷：輸出鏈表數(shù)據(jù)

 @Override
    public String toString() {
        StringBuilder res = new StringBuilder();

        Node cur = dummyHead.next;
        while (cur!=null){
            res.append(cur + "->");
            cur = cur.next;
        }
        res.append("Null");

        return  res.toString();
    }

8. 刪除元素

刪除索引2位置的元素

如果想要?jiǎng)h除索引為2的位置的元素，我們只需要找到這個(gè)目標(biāo)刪除節(jié)點(diǎn)delNode的上一個(gè)節(jié)點(diǎn)prev，讓prev的next指針指向原來delNode的next指針指向的節(jié)點(diǎn)，然后將delNode節(jié)點(diǎn)的next指針指向null即可

• 刪除索引index位置的元素

    // 刪除元素
    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;
    }

• 刪除鏈表第一個(gè)元素和最后一個(gè)元素

    // 從鏈表中刪除第一個(gè)元素，返回刪除的元素
    public E removeFirst(){
        return remove(0);
    }
    
    // 從鏈表中刪除最后一個(gè)元素，返回刪除的元素
    public E removeLast(){
        return  remove(size -1);
    }

9. 測(cè)試

public class Test_Linkedlist {
    public static void main(String[] args){
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i <5 ; i++) {
            linkedList.addFirst(i);
            System.out.println(linkedList.toString());
        }
        linkedList.set(2,666);
        System.out.println(linkedList.toString());

        Integer integer = linkedList.get(2);
        System.out.println("索引2的位置的元素為："+integer);

        linkedList.remove(2);
        System.out.println(linkedList.toString());

        linkedList.removeFirst();
        System.out.println(linkedList.toString());

        linkedList.removeLast();
        System.out.println(linkedList.toString());
    }
}

0->Null
1->0->Null
2->1->0->Null
3->2->1->0->Null
4->3->2->1->0->Null
4->3->666->1->0->Null
索引2的位置的元素為：666
4->3->1->0->Null
3->1->0->Null
3->1->Null

10. 時(shí)間復(fù)雜度分析

• 添加操作：O(n)
  ① addLast(e)---O(n)
  ② addFirst(e)---O(1)
  ③ add(index,e)---O(n)
• 刪除操作：O(n)
  ① removeLast---O(n)
  ② removeFirst---O(1)
  ③ remove(index,e)---O(n)
• 查找操作：O(n)
  ① get(index)---O(n)
  ② contains(e)---O(n)

• 修改操作：O(n)
  ① set(index,e)---O(n)
  綜上：增刪改查都是O(n)，總體而言是比數(shù)組的性能要差的，所以它適合以下場(chǎng)景的操作：

  
  
  鏈表應(yīng)用場(chǎng)景

11. 后續(xù)

如果大家喜歡這篇文章，歡迎點(diǎn)贊！
如果想看更多 數(shù)據(jù)結(jié)構(gòu) 方面的文章，歡迎關(guān)注!