1.ArrayList的缺點

上篇文章我們已經(jīng)對順序表進行了實現(xiàn),并且對ArrayList進行了使用,我們知道ArrayList底層是使用數(shù)組實現(xiàn)的.
由于其底層是一段連續(xù)空間，當(dāng)在ArrayList任意位置插入或者刪除元素時，就需要將后序元素整體往前或者往后搬移，時間復(fù)雜度為O(n)，效率比較低，因此ArrayList不適合做任意位置插入和刪除比較多的場景。因此：java集合中又引入了LinkedList，即鏈表結(jié)構(gòu)。

2.鏈表

2.1 鏈表的概念與結(jié)構(gòu)

鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的引用鏈接次序實現(xiàn)的.就像一列動車一樣.


通過上圖我們可以看到,一個鏈表中有一節(jié)一節(jié)的"車廂",還有中間的"鏈條".我們稱每一節(jié)"車廂"為結(jié)點,我們可以看到每一個結(jié)點中有下一個結(jié)點的地址,鏈表就是通過存儲節(jié)點的地址來連接起來的,還有該結(jié)點的值.上面就是我們需要重點掌握的一種鏈表類型,叫做單向無頭非循環(huán)鏈表.其實鏈表還有好多類型,下面我們來展示.

2.2 鏈表的類型

鏈表有以下幾種性質(zhì):有頭/無頭,單向/雙向,循環(huán)/非循環(huán)

1. 有頭/無頭
   
   
   它們的區(qū)別就是,有頭鏈表的head永遠指向一個固定的結(jié)點,而無頭鏈表的head永遠在改變.
2. 單向/雙向
   

3. 循環(huán)/非循環(huán)


上面幾種性質(zhì)排列組合可以得到許多中鏈表的類型,這里我們重點掌握2中即可,一種是單向無頭非循環(huán),它在筆面試中經(jīng)常出現(xiàn),另一種是是無頭雙向非循環(huán)鏈表,Java中的LinkedList底層就是通過它來實現(xiàn)的.

3. 單向無頭非循環(huán)鏈表實現(xiàn)

下面是要實現(xiàn)的接口,即鏈表中的常用方法:

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

}

下面我們來實現(xiàn)這些方法:

public class MyLinkedList implements ILinkedList {
    static class Node{
        public int val;
        public Node next = null;
        public Node(int val) {
            this.val = val;
        }
    }
    public Node head = null;

    /**
     * 創(chuàng)建默認鏈表
     */
    public void createDeafultLinkedList(){
        Node node = new Node(23);
        this.head = node;
        Node node1 = new Node(34);
        node.next = node1;
        Node node2 = new Node(45);
        node1.next = node2;
        Node node3 = new Node(56);
        node2.next = node3;
        Node node4 = new Node(67);
        node3.next = node4;
    }

    /**
     * 在鏈表頭部添加新的結(jié)點
     * @param data
     */
    @Override
    public void addFirst(int data) {
        Node node = new Node(data);
//        if(head == null){
//            head = node;
//        }else {
//            node.next = head;
//            head = node;
//        }
        //上面的代碼其實沒必要驗證鏈表是否為空,head為null賦值過去還是null
        node.next = this.head;
        this.head = node;
    }

    /**
     * 在尾部添加新的結(jié)點
     * @param data
     */
    @Override
    public void addLast(int data) {
        Node node = new Node(data);
        Node cur = this.head;
        if (this.head == null){
            this.head = node;
        }else {
            while (cur.next != null){
                cur = cur.next;
            }
            cur.next = node;
        }
    }

    /**
     * 在指定位置添加結(jié)點
     * @param index
     * @param data
     */
    @Override
    public void addIndex(int index, int data) {
        if (index > size() || index < 0){
            throw new IndexExeption("下標有誤");
        }
        Node node = new Node(data);
        if (this.head == null){
            this.head = node;
            return;//記得返回,不然會執(zhí)行中間插入的代碼
        }
        if (index == 0){//在鏈表頭添加
            addFirst(node.val);
            return;
        }
        if (index == size()){//在鏈表尾部添加
            addLast(node.val);
            return;
        }
        //在中部添加
        Node cur = this.head;
        int count = 0;
        while (count != index-1){//尋找cur的前一個結(jié)點
            cur = cur.next;
            count++;
        }
        node.next = cur.next;
        cur.next = node;
    }

    /**
     * 檢測鏈表中是否含有指定的值
     * @param key
     * @return
     */
    @Override
    public boolean contains(int key) {
        Node cur = this.head;
        while (cur != null){//先遍歷鏈表
            if(cur.val == key){//在遍歷的過程中如果等于,返回true
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    /**
     * 移除遇到的第一個值為key的元素
     * @param key
     */
    @Override
    public void remove(int key) {
        if (this.head == null){
            return;
        }
        if (head.val == key){
            head = head.next;
            return;
        }
        Node cur = findPreNode(key);//需要找到前一個結(jié)點才可以刪除
        if (cur == null){//沒找到要刪除的結(jié)點
            return;
        }
        cur.next = cur.next.next;
    }
    private Node findPreNode(int key){//找到要刪除結(jié)點的前一個結(jié)點
        Node cur = this.head;
        while (cur.next != null){//這里必須寫成next不等于null,否則下面可能會出現(xiàn)空指針異常
            if (cur.next.val == key){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    /**
     * 移除所有符合值為key的結(jié)點
     * @param key
     */

    @Override
    public void removeAllKey(int key) {
        if (this.head == null){
            return;
        }
        Node pre = this.head;
        Node cur = this.head.next;
        //先不要管頭結(jié)點,先刪中間的
        while(cur != null){
            if (cur.val == key){
                pre.next = cur.next;
            }else {
                pre = pre.next;//若該結(jié)點不是要刪除的結(jié)點,pre往后走
            }
            cur = cur.next;
        }
        //所有的都刪完了,刪除頭結(jié)點
        if (head.val == key){
            head = head.next;
        }
    }

    /**
     * 計算鏈表大小
     * @return
     */
    @Override
    public int size() {
        int count = 0;
        Node cur = this.head;
        while (cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }

    /**
     * 清空鏈表
     */
    @Override
    public void clear() {
        head = null;//為被引用的結(jié)點會被JWM回收
    }

    /**
     * 打印鏈表
     */
    @Override
    public void display() {
        Node cur = this.head;
        while (cur != null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

    /**
     * 從指定位置開始打印鏈表
     * @param node
     */
    public void display(Node node) {
        Node cur = node;
        while (cur != null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

}

上面有幾個問題需要注意

1. 在中間插入元素的時候先要進行后鏈接,在進行前鏈接,如果先進行前鏈接,cur的下一個結(jié)點的地址就會丟失
2. 在刪除所有值為key的結(jié)點的時候,先刪除head后符合條件的結(jié)點最后再處理head.

下面是對上述問題的動態(tài)演示:

[插入結(jié)點錯誤演示]

[插入結(jié)點正確演示]

[刪除所有key結(jié)點]

下面我們對上述實現(xiàn)的方法進行測試:

**
 * 開始測試
 */
public class Test {
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.createDeafultLinkedList();
        myLinkedList.addFirst(11);
        myLinkedList.addLast(88);
        myLinkedList.display();
        System.out.println(myLinkedList.size());
        myLinkedList.addIndex(2,33);
        myLinkedList.display();
        System.out.println(myLinkedList.contains(11));
        System.out.println(myLinkedList.contains(12));
        myLinkedList.addIndex(1,23);
        myLinkedList.addIndex(1,23);
        myLinkedList.addIndex(1,23);
        myLinkedList.display();
        myLinkedList.remove(23);
        myLinkedList.display();
        myLinkedList.removeAllKey(23);
        myLinkedList.display();
        myLinkedList.clear();
        myLinkedList.display();
    }
}

測試結(jié)果:
文章來源地址http://www.zghlxwxcb.cn/news/detail-858484.html

到了這里，關(guān)于[Collection與數(shù)據(jù)結(jié)構(gòu)] 鏈表與LinkedList (一):鏈表概述與單向無頭非循環(huán)鏈表實現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！