java數(shù)據(jù)結(jié)構(gòu)基礎(chǔ):單,雙向鏈表

更新時(shí)間：2021年07月27日 15:37:40 作者：魚小洲

這篇文章主要介紹了Java的數(shù)據(jù)解構(gòu)基礎(chǔ)，希望對(duì)廣大的程序愛好者有所幫助，同時(shí)祝大家有一個(gè)好成績(jī),需要的朋友可以參考下，希望能給你帶來幫助

單向鏈表

單向鏈表比順序結(jié)構(gòu)的線性表最大的好處就是不用保證存放的位置，它只需要用指針去指向下一個(gè)元素就能搞定。

單鏈表圖解

在這里插入圖片描述

圖畫的比較粗糙，簡(jiǎn)單的講解一下：

上面四個(gè)長方形，每個(gè)長方形都是一個(gè)節(jié)點(diǎn)。在長方形中，一種包含兩個(gè)東西，一個(gè)是當(dāng)前節(jié)點(diǎn)的元素，一個(gè)是指向下一節(jié)點(diǎn)的地址。這個(gè)下一個(gè)節(jié)點(diǎn)的地址指向了下一個(gè)節(jié)點(diǎn)中的元素。以此類推。

在最左邊的叫做頭節(jié)點(diǎn)，同樣，最后面的叫尾節(jié)點(diǎn)。

所以，我們所有的操作都是根據(jù)節(jié)點(diǎn)來進(jìn)行操作。

代碼

這些代碼都有很詳細(xì)的注釋，我就不做過多的解釋了，你直接復(fù)制代碼到本地idea運(yùn)行一遍就全部知道了。

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

雙向鏈表

昨天寫完單向鏈表和棧結(jié)構(gòu)之后，看了看程杰大大的書中有介紹雙向鏈表的部分。雖然是c語言寫的，但是我還是用Java給翻譯出來了。

思路如下：

首先，雙向鏈表和單向鏈表的最大區(qū)別就是，雙向鏈表比單鏈表多了個(gè)指向前一節(jié)點(diǎn)的指針。代碼量其實(shí)并不比單鏈表多很多，只是思路的轉(zhuǎn)變需要克服一下。

其次就是在插入元素的時(shí)候，我們可以在鏈表的頭部插入，也可以在鏈表的尾部插入（因?yàn)橛袃蓚€(gè)指針嘛）

編碼

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

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

    /**
     * 定義雙向鏈表節(jié)點(diǎn)對(duì)象
     */
    class Node<E> {
        E item; // 記錄元素
        Node<E> prev; // 記錄前一個(gè)節(jié)點(diǎn)對(duì)象
        Node<E> next; // 記錄下一個(gè)節(jié)點(diǎn)對(duì)象
        public Node(Node<E> prev, E item, Node<E> next) {
            this.item = item;
            this.prev = prev;
            this.next = next;
        }
    }
    private Node head; // 記錄頭節(jié)點(diǎn)
    private Node tail; // 記錄尾節(jié)點(diǎn)
    private int size; // 記錄元素個(gè)數(shù)
    /**
     * 向雙向鏈表中添加元素的方法
     *
     * @param element
     */
    @Override
    public void add(E element) {
        linkLast(element);
    }
    /**
     * 將節(jié)點(diǎn)對(duì)象添加到雙向鏈表的尾部
     */
    private void linkLast(E element) {
        Node t = this.tail; // 獲取尾節(jié)點(diǎn)
        Node<E> node = new Node<>(t, element, null); // 創(chuàng)建節(jié)點(diǎn)對(duì)象
        this.tail = node; // 將新節(jié)點(diǎn)定義為尾節(jié)點(diǎn) 因?yàn)樵瓉淼奈补?jié)點(diǎn)被這個(gè)新節(jié)點(diǎn)替代了
        if (t == null) {
            // 說明一個(gè)節(jié)點(diǎn)都沒有，這個(gè)還得是頭節(jié)點(diǎn)
            this.head = node;
        } else {
            t.next = node;
        }
        this.size++;
    }
    /**
     * 根據(jù)指定位置獲取元素
     *
     * @param index
     * @return
     */
    @Override
    public E get(int index) {
        this.checkIndex(index);
        // 根據(jù)位置查找節(jié)點(diǎn)對(duì)象
        Node<E> node = this.getNode(index);
        return node.item;
    }
    /**
     * 對(duì)index的合法性校驗(yàn)
     */
    private void checkIndex(int index) {
        if (!(index >= 0 && index < this.size)) {
            throw new IndexOutOfBoundsException();
        }
    }
    /**
     * 根據(jù)位置獲取指定節(jié)點(diǎn)對(duì)象
     */
    private Node getNode(int index) {
        // 判斷當(dāng)前位置距離頭或者尾哪個(gè)節(jié)點(diǎn)更近  使用二分法
        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;
        }
    }
    /**
     * 返回元素的個(gè)數(shù)
     *
     * @return
     */
    @Override
    public int size() {
        return this.size;
    }
    /**
     * 刪除元素
     *
     * @param index
     * @return
     */
    @Override
    public E remove(int index) {
        // 對(duì)index進(jìn)行合法性校驗(yàn)
        this.checkIndex(index);
        Node node = this.getNode(index); // 根據(jù)位置獲取到節(jié)點(diǎn)對(duì)象
        // 獲取節(jié)點(diǎn)對(duì)象的元素
        E item = (E) node.item;
        // 判斷當(dāng)前節(jié)點(diǎn)是否為頭節(jié)點(diǎn)
        if (node.prev == null) {
            this.head = node.next;
        } else {
            node.prev.next = node.next;
        }
        // 判斷當(dāng)前節(jié)點(diǎn)是否為尾節(jié)點(diǎn)
        if (node.next == null) {
            // node.prev.next = null;
            this.tail = node.prev;
        } else {
            node.next.prev = node.prev;
        }
        // 當(dāng)前節(jié)點(diǎn)斷掉與他后繼節(jié)點(diǎn)的連接
        node.next = null;
        // 當(dāng)前節(jié)點(diǎn)斷掉與直接前驅(qū)節(jié)點(diǎn)的連接
        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) {
        // 獲取頭節(jié)點(diǎn)對(duì)象
        Node head = this.head;
        Node<E> eNode = new Node<>(null, element, head);
        // 將新節(jié)點(diǎn)定義為頭節(jié)點(diǎn)
        this.head = eNode;
        if (head == null) {
            // 如果為空，說明該鏈表中一個(gè)節(jié)點(diǎn)都沒有 也就是該頭節(jié)點(diǎn)也是尾節(jié)點(diǎn)
            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));
        }
    }
}