數據結構(4):鏈表的原理和實現

上、簡單的單端鏈表

完整代碼向下拉

鏈表是一種常用的數據結構,在插入和移除操作中有著優秀的表現,同為數據結構的數組哭暈,其實數組的訪問效率比鏈表高多了有木有。

我們先看一下鏈表的樣子

鏈表示意圖

有同學可能要說了,這不就是我們生活中的交通工具——火車,沒錯鏈表的結構和下圖簡直就是一個模子刻出來的。(咳咳,忽略這靈魂的畫法)

火車車廂

通過火車示意圖可以觀察到,火車由火車頭和n節車廂組成,每節車廂都與下一節車廂相連,能理解這句話,鏈表你就掌握一半了。

以小學掌握的物品分類知識來對上圖進行面向對象抽象,火車整體可以認為是鏈表,火車又由車廂組成的,同樣可以理解鏈表是由節點組成的,鏈表起到了組合節點的作用。

1、創建節點(車廂)

車廂都有哪些特點呢?車廂能存放物品,車廂與下一節車廂相連。

public class Node {
    public Object data;//存放的數據
    public Node next;//指向下一個節點

    public Node(Object value) {
        this.data = value;
    }

    //展示節點數據
    public void display() {
        System.out.print(data+" ");
    }
}

2、創建鏈表(將車廂組合)

在現實中我們要想查看整個火車由一個十分暴力的方法,那就是找到火車頭,找到火車頭后沿著每節車廂向后查找就可以完整的查看整輛火車。

public class LinkList {
    private Node first;//第一個節點
}

在代碼中 Node 類已經聲明了指向下一個節點的屬性,所以只需要找到第一個節點,調用next屬性即可無限向后查找。

3、判斷鏈表是否為空

第一個節點為空即為鏈表為空

public boolean isEmpty() {
    return first == null;
}

4、添加數據到鏈表的頭部

添加數據到鏈表頭部,就是將新節點的next指向原來的首節點,再將新節點標記為first即可。

public void addFirst(Object value) {
    Node newNode = new Node(value);//創建新節點
    if (isEmpty()) {
        first = newNode;//沒有節點時直接標記為首節點
    } else {
        newNode.next = first;//新節點next指向舊的首節點
        first = newNode;
    }
}

5、移除首節點

并非真正意義上的移除,而是將first指向first.next的內存地址,而原來的first會被垃圾回收器回收。

移除首節點示意圖

public Node removeFirst() {
    if (isEmpty()) {
        return null;
    }
    Node tmp = first;
    first = first.next;
    return tmp;
}

6、查看鏈表

由于鏈表中的每個節點都有變量指向下一個節點,所有可以使用循環遞進獲取下一個節點實現遍歷的效果。

public void display() {
    Node current = first;//先從首節點開始
    while (current != null) {
        current.display();//節點不為空,則打印該節點信息
        current = current.next;//獲取當前節點的下個節點重新放入current中
        System.out.println();
    }
}

7、根據值查找鏈表中的節點

需要遍歷節點,將每個節點的值都與要查找的值進行比對,如果值不相等就一直循環,直到最后一個節點為空時表示沒有查到。

public Node find(Object value) {
    if (isEmpty()) {
        return null;
    }
    Node current = first;
    while (current.data != value) {
        if (current.next==null){
            return null;
        }
        current = current.next;
    }
    return current;
}

8、根據值移除節點

移除時同樣遍歷所有節點,但要保存查到節點的之前節點(previous),如果查到的節點是第一個節點,直接移除第一個,否則就將前一個節點指向要移除節點的下一個。

根據值移除節點

public Node remove(Object value){
    if (isEmpty()) {
        return null;
    }
    Node current = first;
    Node previous = first;
    while (current.data != value) {
        if (current.next==null){
            return null;
        }
        previous = current;
        current = current.next;
    }
    if (current==first){
        removeFirst();
    }else{
        previous.next=current.next;
    }

    return current;
}

9、完整代碼

public class LinkList {
    private Node first;//第一個節點

    public void addFirst(Object value) {
        Node newNode = new Node(value);//創建新節點
        if (isEmpty()) {
            first = newNode;//沒有節點時直接標記為首節點
        } else {
            newNode.next = first;//新節點next指向舊的首節點
            first = newNode;
        }
    }

    public Node removeFirst() {
        if (isEmpty()) {
            return null;
        }
        Node tmp = first;
        first = first.next;
        return tmp;
    }

    public void display() {
        Node current = first;//先從首節點開始
        while (current != null) {
            current.display();//節點不為空,則打印該節點信息
            current = current.next;//獲取當前節點的下個節點重新放入current中
            System.out.println();
        }
    }

    public Node find(Object value) {
        if (isEmpty()) {
            return null;
        }
        Node current = first;
        while (current.data != value) {
            if (current.next==null){
                return null;
            }
            current = current.next;
        }
        return current;
    }
    public Node remove(Object value){
        if (isEmpty()) {
            return null;
        }
        Node current = first;
        Node previous = first;
        while (current.data != value) {
            if (current.next==null){
                return null;
            }
            previous = current;
            current = current.next;
        }
        if (current==first){
            removeFirst();
        }else{
            previous.next=current.next;
        }

        return current;
    }

    public boolean isEmpty() {
        return first == null;
    }

    public static void main(String[] args) {
        LinkList linkList = new LinkList();
        linkList.addFirst("a");
        linkList.addFirst("b");
        System.out.println("-0---");
        linkList.remove("a");
        linkList.display();

    }

    public class Node {
        public Object data;//存放的數據
        public Node next;//指向下一個節點

        public Node(Object value) {
            this.data = value;
        }

        //展示節點數據
        public void display() {
            System.out.print(data+" ");
        }
    }
}

單端鏈表還是有一些不足,比如我們要操作最后一個節點需要遍歷整個鏈表,下一節咱們實現雙端鏈表,提高操作最后一個節點的效率。

中、操作更簡單的雙端鏈表

上節文章中咱們了解了鏈表的結構及原理,但是還有些美中不足的地方,就是無法快速的訪問鏈表中的最后一個節點。
在這節文章中咱們來解決這個問題,一起來吧。

首先先看如何快速訪問尾節點,其實這個可以通過一個變量指向尾節點,在做插入、刪除時更新尾節點即可。

雙端鏈表

1、創建節點

節點用于存儲數據和下一個節點相連

public class Node {
    public Object data;//存放的數據
    public Node next;//指向下一個節點

    public Node(Object value) {
        this.data = value;
    }

    //展示節點數據
    public void display() {
        System.out.print(data + " ");
    }
}

2、創建鏈表

操作節點和指向首尾兩個節點

public class DoubleEndLinkList {
    private Node first;//第一個節點
    private Node last;//最后一個節點
}

3、向前添加節點

如果加入的節點是第一個節點,這個節點是首節點同時也是尾節點。如果已經有節點則讓新節點指向原來的首節點,讓首節點指向新節點。

向前添加節點

public void addFirst(Object value) {
    Node newNode = new Node(value);
    if (isEmpty()) {
        //如果為空,尾節點指向此節點
        last = newNode;
    }
    //更替新節點
    newNode.next = first;
    first = newNode;
}

4、向后添加節點

和向前添加相反,因為鏈表中last始終指向最后一個節點,所以操作last節點。

public void addLast(Object value) {
    Node newNode = new Node(value);
    if (isEmpty()) {
        //如果為空,首節點和尾節點指向此節點
        first = newNode;
        last = newNode;
        return;
    }
    //更替尾節點
    last.next = newNode;
    last = newNode;
}

5、移除首節點

移除首節點時將首節點的下一個節點標記為首節點即可,直到首節點與尾節點相同時(這時也意味這只剩一個節點)不再需要輪替,直接將首尾節點設置為null。

public Node removeFirst() {
    if (isEmpty()) {
        return null;
    }
    Node tmp = first;
    //僅剩一個節點時
    if (first == last) {
        first = null;
        last = null;
        return tmp;
    }
    //無論有多少個節點都會輪替到first==last
    first = first.next;

    return tmp;
}

6、完整代碼

package com.jikedaquan.datastruct;

public class DoubleEndLinkList {
    private Node first;//第一個節點
    private Node last;//最后一個節點

    public void addFirst(Object value) {
        Node newNode = new Node(value);
        if (isEmpty()) {
            //如果為空,尾節點指向此節點
            last = newNode;
        }
        //更替新節點
        newNode.next = first;
        first = newNode;
    }

    public void addLast(Object value) {
        Node newNode = new Node(value);
        if (isEmpty()) {
            //如果為空,首節點和尾節點指向此節點
            first = newNode;
            last = newNode;
            return;
        }
        //更替尾節點
        last.next = newNode;
        last = newNode;
    }

    public Node removeFirst() {
        if (isEmpty()) {
            return null;
        }
        Node tmp = first;
        //僅剩一個節點時
        if (first == last) {
            first = null;
            last = null;
            return tmp;
        }
        //無論有多少個節點都會輪替到first==last
        first = first.next;

        return tmp;
    }


    public void display() {
        Node current = first;//先從首節點開始
        while (current != null) {
            current.display();//節點不為空,則打印該節點信息
            current = current.next;//獲取當前節點的下個節點重新放入current中
            System.out.println();
        }
    }

    public boolean isEmpty() {
        return first == null;
    }

    public static void main(String[] args) {
        DoubleEndLinkList linkList = new DoubleEndLinkList();
        linkList.addLast("e");
        linkList.addFirst("a");
        linkList.addFirst("b");
        linkList.removeFirst();
        linkList.removeFirst();
        linkList.removeFirst();
        linkList.display();
        System.out.println("-0---");
        linkList.addLast("c");
        linkList.addFirst("1");
        linkList.display();
        System.out.println("-0---");
        linkList.removeFirst();
        linkList.removeFirst();

        linkList.addLast(9);
        linkList.display();
        System.out.println("-0---");
        linkList.display();
    }

    public class Node {
        public Object data;//存放的數據
        public Node next;//指向下一個節點

        public Node(Object value) {
            this.data = value;
        }

        //展示節點數據
        public void display() {
            System.out.print(data + " ");
        }
    }
}

雙端鏈表能同時向首尾添加新元素,用雙端鏈表實現隊列也成為了可能(比用數組實現效率更高),但是如何快速移除最后一個元素(因為不能快速的追溯之前的元素)成為了一個新難題,請看下一節 雙向鏈表!

下、方便高效的雙向鏈表

單向鏈表每個節點指向下一個節點,而雙向鏈表是指每個節點還指向了前一個節點。這樣做的好處是可以快速的移除最后一個元素。

雙向鏈表

1、保存數據的節點

節點除了指向下一個節點還要指向前一個節點

public class Node {
    public Object data;//存放的數據

    public Node previous;//指向前一個節點
    public Node next;//指向下一個節點

    public Node(Object value) {
        this.data = value;
    }

    //展示節點數據
    public void display() {
        System.out.print(data + " ");

    }
}

2、創建鏈表指向首元素和尾元素

public class TwoWayLinkList {
    private Node first;
    private Node last;
}

3、向前添加元素

考慮到鏈表為空時,首元素和尾元素均指向新元素。

public void addFirst(Object value) {
    Node newNode = new Node(value);
    if (isEmpty()) {
        last = newNode;
        first = newNode;
        return;
    }
    //新首元素指向舊首元素
    newNode.next = first;
    //舊首元素的前一個指向新首元素
    first.previous = newNode;
    //更替首元素
    first = newNode;
}

4、向后添加元素

由于是雙向的,所以之前的引用和之后的引用都要更新

public void addLast(Object value) {
    Node newNode = new Node(value);
    if (isEmpty()) {
        first = newNode;
        last = newNode;
        return;
    }
    //更替尾元素
    newNode.previous = last;
    last.next = newNode;
    last = newNode;
}

5、移除首元素

如果過已是最后一個元素,直接將首尾設置為null,其他情況進行輪替。

移除首元素示意圖

public Node removeFirst() {
    Node removeNode = first;
    //如果當前已是最后一個元素
    if (first.next == null) {
        first = null;
        last = null;
        return removeNode;
    }
    //首元素指向下一個元素
    first = first.next;
    //將新首元素指向的之前的元素設為null
    first.previous = null;

    return removeNode;
}

6、移除尾元素

和移除首元素類似

移除尾元素示意圖

public Node removeLast() {
    Node removeNode = last;
    if (last.previous == null) {
        first = null;
        last = null;
        return null;
    }
    //尾元素指向舊尾元素之前的元素
    last = last.previous;
    //將新尾元素的下一個元素設為null
    last.next = null;
    return removeNode;
}

7、根據值移除節點

從第一個元素開始遍歷,如果值不相同就一直遍歷,沒有元素匹配返回null,有元素相同時將之前的元素指向當前元素的下一個,將當前元素下一個指向前一個。

public Node remove(Object value) {
    if (isEmpty()){
        return null;
    }
    Node current = first;
    while (current.data != value) {
        if (current.next == null) {
            return null;
        }
        current = current.next;
    }
    current.previous.next = current.next;
    current.next.previous = current.previous;
    return current;
}

8、完整代碼

package com.jikedaquan.datastruct;

public class TwoWayLinkList {
    private Node first;
    private Node last;

    public void addFirst(Object value) {
        Node newNode = new Node(value);
        if (isEmpty()) {
            last = newNode;
            first = newNode;
            return;
        }
        //新首元素指向舊首元素
        newNode.next = first;
        //舊首元素的前一個指向新首元素
        first.previous = newNode;
        //更替首元素
        first = newNode;
    }

    public void addLast(Object value) {
        Node newNode = new Node(value);
        if (isEmpty()) {
            first = newNode;
            last = newNode;
            return;
        }
        //更替尾元素
        newNode.previous = last;
        last.next = newNode;
        last = newNode;
    }

    public Node removeFirst() {
        Node removeNode = first;
        //如果當前已是最后一個元素
        if (first.next == null) {
            first = null;
            last = null;
            return removeNode;
        }
        //首元素指向下一個元素
        first = first.next;
        //將新首元素指向的之前的元素設為null
        first.previous = null;

        return removeNode;
    }

    public Node removeLast() {
        Node removeNode = last;
        if (last.previous == null) {
            first = null;
            last = null;
            return null;
        }
        //尾元素指向舊尾元素之前的元素
        last = last.previous;
        //將新尾元素的下一個元素設為null
        last.next = null;
        return removeNode;
    }

    public Node remove(Object value) {
        if (isEmpty()){
            return null;
        }
        Node current = first;
        while (current.data != value) {
            if (current.next == null) {
                return null;
            }
            current = current.next;
        }
        current.previous.next = current.next;
        current.next.previous = current.previous;
        return current;
    }

    public boolean isEmpty() {
        return first == null;
    }

    public void display() {
        Node current = first;//先從首節點開始
        while (current != null) {
            current.display();//節點不為空,則打印該節點信息
            current = current.next;//獲取當前節點的下個節點重新放入current中
        }
        System.out.println();
    }

    public static void main(String[] args) {
        TwoWayLinkList linkList = new TwoWayLinkList();
        linkList.addFirst("b");
        linkList.addFirst("a");
        linkList.display();
        System.out.println("======");
        while (!linkList.isEmpty()) {
            linkList.removeFirst();
            linkList.display();
        }
        System.out.println("======");
        linkList.addLast("c");
        linkList.addLast("d");
        linkList.display();
        System.out.println("======");
        while (!linkList.isEmpty()) {
            linkList.removeLast();
            linkList.display();
        }
        System.out.println("======");
        linkList.addFirst("e");
        linkList.addLast("f");
        linkList.addLast("g");
        linkList.display();
        System.out.println("======");
        linkList.remove("f");
        System.out.println("======");
        linkList.display();

    }

    public class Node {
        public Object data;//存放的數據

        public Node previous;//指向前一個節點
        public Node next;//指向下一個節點

        public Node(Object value) {
            this.data = value;
        }

        //展示節點數據
        public void display() {
            System.out.print(data + " ");

        }
    }
}

9、總結

鏈表是節點中通過變量指向前一個節點和下一個節點實現了相連,鏈表在移除節點、首尾添加節點有著優越的性能,時間復雜度O(1)。數組在做同等操作需要O(n),但在訪問元素上優于鏈表,空間復雜度也小于鏈表,應在不同的場景選用不同的結構。
當然這些數據結構也不需要我們去實現的,java語言中已經有對應的實現。

posted @ 2019-10-04 09:09 極客大全 閱讀(...) 評論(...) 編輯 收藏
我要啦免費統計
u视娱乐