java數據結構基礎:單,雙向鏈表

單向鏈表

單向鏈表比順序結構的線性表最大的好處就是不用保證存放的位置,它隻需要用指針去指向下一個元素就能搞定。

單鏈表圖解

在這裡插入圖片描述

圖畫的比較粗糙,簡單的講解一下:

上面四個長方形,每個長方形都是一個節點。在長方形中,一種包含兩個東西,一個是當前節點的元素,一個是指向下一節點的地址。這個下一個節點的地址指向瞭下一個節點中的元素。以此類推。

在最左邊的叫做頭節點,同樣,最後面的叫尾節點。

所以,我們所有的操作都是根據節點來進行操作。

代碼

這些代碼都有很詳細的註釋,我就不做過多的解釋瞭,你直接復制代碼到本地idea運行一遍就全部知道瞭。

package com.zxy.lianbiao;
/**
 * @Author Zxy
 * @Date 2021/2/3 21:25
 * @Version 1.0
 */
/**
 * 基於單向鏈表實現元素的存取
 *
 * @param <E>
 */
public class MySinglyLinkedList<E> implements MyList<E> {
    /**
     * 定義單向鏈表中的節點對象
     */
    class Node<E> {
        private E item; // 存儲元素
        private Node next; // 存儲下一個節點對象
        public Node(E item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
    private Node head; // 存放鏈表中的頭節點
    private int size; // 記錄元素的個數
    /**
     * 向鏈表中添加元素
     *
     * @param element
     */
    @Override
    public void add(E element) {
        // 創建節點
        Node<E> node = new Node<>(element, null);
        // 找到尾節點
        Node tail = getTail();
        // 節點的掛接
        if (tail == null) { // 如果沒有尾節點,那意思就是頭節點都不存在
            // 沒有頭節點,那麼就把創建的節點給頭節點
            this.head = node;
        } else {
            tail.next = node;
        }
        // 記錄元素的個數
        this.size++;
    }
    /**
     * 找尾節點
     */
    private Node getTail() {
        // 判斷頭節點是否存在
        if (this.head == null) {
            return null;
        }
        // 查找尾節點
        Node node = this.head;
        while (true) {
            if (node.next == null) {
                break;
            }
            node = node.next; // 移動指針指向下一個
        }
        return node;
    }
    /**
     * 根據元素的位置獲取元素
     *
     * @param index
     * @return
     */
    @Override
    public E get(int index) {
        // 校驗index的合法性
        this.checkIndex(index);
        // 根據位置獲取指定節點
        Node<E> node = this.getNode(index);
        // 將該節點中的元素返回
        return node.item;
    }
    /**
     * 對index進行校驗
     */
    private void checkIndex(int index) {
        // 0<=index<size
        if (!(index >= 0 && index < this.size)) {
            throw new IndexOutOfBoundsException("Index: " + index + "   this.size: " + this.size);
        }
    }
    /**
     * 根據位置獲取節點
     */
    private Node<E> getNode(int index) {
        Node<E> node = this.head;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }
    /**
     * 獲取元素的個數
     *
     * @return
     */
    @Override
    public int size() {
        return this.size;
    }
    /**
     * 根據元素位置刪除元素
     *
     * @param index
     * @return
     */
    @Override
    public E remove(int index) {
        // 校驗index合法性
        this.checkIndex(index);
        // 根據位置找到節點對象
        Node<E> node = getNode(index);
        // 獲取該節點對象中的元素
        E item = node.item;
        // 將該節點對象從單向鏈表中移除
        // 判斷當前刪除的節點是否為頭節點
        if (this.head == node) {
            this.head = node.next;
        } else {
            Node<E> temp = this.head;
            for (int i = 0; i < index - 1; i++) {
                temp = temp.next; // 此時的temp就是要刪除的那個節點的前一個節點
            }
            temp.next = node.next; // 將當前節點的前一個節點指向當前節點的後一個節點
        }
        // 然後將當前節點的下一個節點指向null
        node.next = null;
        // 記錄元素個數
        this.size--;
        // 將該元素返回
        return item;
    }
    /**
     * 插入節點思路:如果當前共有三個節點分別是1,2,3,在1和2的中間插入4,原本的指向是1->2 現改變成1->4 4->2 先獲取到指定位置的node,再獲取到前一個位置的node和下一個位置的node
     */
    public void insert(int index, E element) {
        // 先根據要插入的位置拿到這個位置的節點對象
        Node<E> item = getNode(index);
        // 根據插入的元素新建一個節點
        Node<E> eNode = new Node<>(element, null);
        // 如果是頭節點,那麼就找不到前一個,直接把這個賦值給head
        if (index == 0){
            // index==0代表是替換掉頭節點
            this.head = eNode;
            eNode.next = item;
            this.size++;
        }else {
            // 根據當前的節點對象去找到前一個節點對象和後一個節點對象
            Node<E> before = this.head; // 根據頭節點去找
            for (int i = 0; i < index - 1; i++) {
                before = before.next; // 此時的before就是當前節點的前一個節點
            }
            before.next = eNode;
            eNode.next = item;
            this.size++;
        }
    }
    public static void main(String[] args) {
        MySinglyLinkedList<String> list = new MySinglyLinkedList<>();
        System.out.println("添加節點開始------------------------");
        list.add((String) "a");
        list.add((String) "b");
        list.add((String) "c");
        list.add((String) "d");
        System.out.println("添加節點完成-------------------------\n");
        System.out.println("插入指定的元素");
        list.insert(0,"f");
        for (int i = 0; i < list.size; i++) {
            System.out.println(list.get(i));
        }
    }
}

雙向鏈表

昨天寫完單向鏈表和棧結構之後,看瞭看程傑大大的書中有介紹雙向鏈表的部分。雖然是c語言寫的,但是我還是用Java給翻譯出來瞭。

思路如下:

首先,雙向鏈表和單向鏈表的最大區別就是,雙向鏈表比單鏈表多瞭個指向前一節點的指針。代碼量其實並不比單鏈表多很多,隻是思路的轉變需要克服一下。

其次就是在插入元素的時候,我們可以在鏈表的頭部插入,也可以在鏈表的尾部插入(因為有兩個指針嘛)

編碼

代碼其實和單鏈表差不多,如果感興趣的話可以去看看我之前寫的單鏈表的文章。雖然文筆很爛,但是代碼貨真價實。

package com.zxy.lianbiao;
/**
 * @Author Zxy
 * @Date 2021/2/4 20:11
 * @Version 1.0
 */
/**
 * 基於雙向鏈表實現元素存取的容器
 *
 * @param <E>
 */
public class MyDoublyLinkedList<E> implements MyList<E> {

    /**
     * 定義雙向鏈表節點對象
     */
    class Node<E> {
        E item; // 記錄元素
        Node<E> prev; // 記錄前一個節點對象
        Node<E> next; // 記錄下一個節點對象
        public Node(Node<E> prev, E item, Node<E> next) {
            this.item = item;
            this.prev = prev;
            this.next = next;
        }
    }
    private Node head; // 記錄頭節點
    private Node tail; // 記錄尾節點
    private int size; // 記錄元素個數
    /**
     * 向雙向鏈表中添加元素的方法
     *
     * @param element
     */
    @Override
    public void add(E element) {
        linkLast(element);
    }
    /**
     * 將節點對象添加到雙向鏈表的尾部
     */
    private void linkLast(E element) {
        Node t = this.tail; // 獲取尾節點
        Node<E> node = new Node<>(t, element, null); // 創建節點對象
        this.tail = node; // 將新節點定義為尾節點 因為原來的尾節點被這個新節點替代瞭
        if (t == null) {
            // 說明一個節點都沒有,這個還得是頭節點
            this.head = node;
        } else {
            t.next = node;
        }
        this.size++;
    }
    /**
     * 根據指定位置獲取元素
     *
     * @param index
     * @return
     */
    @Override
    public E get(int index) {
        this.checkIndex(index);
        // 根據位置查找節點對象
        Node<E> node = this.getNode(index);
        return node.item;
    }
    /**
     * 對index的合法性校驗
     */
    private void checkIndex(int index) {
        if (!(index >= 0 && index < this.size)) {
            throw new IndexOutOfBoundsException();
        }
    }
    /**
     * 根據位置獲取指定節點對象
     */
    private Node getNode(int index) {
        // 判斷當前位置距離頭或者尾哪個節點更近  使用二分法
        if (index < (this.size >> 1)) {
            Node node = this.head;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            return node;
        } else {
            Node node = this.tail;
            for (int i = this.size - 1; i > index; i--) {
                node = node.prev;
            }
            return node;
        }
    }
    /**
     * 返回元素的個數
     *
     * @return
     */
    @Override
    public int size() {
        return this.size;
    }
    /**
     * 刪除元素
     *
     * @param index
     * @return
     */
    @Override
    public E remove(int index) {
        // 對index進行合法性校驗
        this.checkIndex(index);
        Node node = this.getNode(index); // 根據位置獲取到節點對象
        // 獲取節點對象的元素
        E item = (E) node.item;
        // 判斷當前節點是否為頭節點
        if (node.prev == null) {
            this.head = node.next;
        } else {
            node.prev.next = node.next;
        }
        // 判斷當前節點是否為尾節點
        if (node.next == null) {
            // node.prev.next = null;
            this.tail = node.prev;
        } else {
            node.next.prev = node.prev;
        }
        // 當前節點斷掉與他後繼節點的連接
        node.next = null;
        // 當前節點斷掉與直接前驅節點的連接
        node.prev = null;
        node.item = null;
        this.size--;
        return item;
    }
    /**
     * 在雙向鏈表的頭添加元素
     */
    public void addFirst(E element) {
        this.linkFirst(element);
    }
    /**
     * 在鏈表的頭添加元素
     *
     * @param element
     */
    public void linkFirst(E element) {
        // 獲取頭節點對象
        Node head = this.head;
        Node<E> eNode = new Node<>(null, element, head);
        // 將新節點定義為頭節點
        this.head = eNode;
        if (head == null) {
            // 如果為空,說明該鏈表中一個節點都沒有 也就是該頭節點也是尾節點
            this.tail = eNode;
        } else {
            head.prev = eNode;
        }
        this.size++;
    }
    /**
     * 在鏈表的尾部添加元素
     *
     * @param element
     */
    public void addLast(E element) {
        this.linkLast(element);
    }
    public static void main(String[] args) {
        MyDoublyLinkedList<String> list = new MyDoublyLinkedList<>();
        list.add("a");
        list.add("b");
        list.add("c");
        list.add("d");
        list.add("e");
        System.out.println(list.remove(2));
        System.out.println(list.size);
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    }
}

總結

本篇文章就到這裡瞭,希望能給你帶來幫助,也希望您能夠多多關註WalkonNet的更多內容!

推薦閱讀: