鏈表

一、單向鏈表

單向鏈表的普通實(shí)現(xiàn)

Java實(shí)現(xiàn):

package linkedlist;
/**
 * 單向鏈表的普通實(shí)現(xiàn)
 *
 * @param <E> E
 * @author ZZX
 */
public class SinglyLinkedList<E> implements LinkedList<E> {
    /**
     * 節(jié)點(diǎn)內(nèi)部類
     */
    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();
        }

    }

    /**
     * 虛擬頭節(jié)點(diǎn)，避免邏輯上區(qū)別處理頭部節(jié)點(diǎn)
     */
    private Node dummyHead;

    private int size;

    public SinglyLinkedList() {
        dummyHead = new Node();
        size = 0;
    }

    public boolean add(int index, E e) {
        if (index < 0 || index > size) {
            return false;
        }

        Node prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
//            Node node = new Node(e);
//            node.next = prev.next;
//            prev.next = node;
        prev.next = new Node(e, prev.next);
        size++;
        return true;
    }

    public E findFirst() {
        return dummyHead.next.e;
    }

    public void addFirst(E e) {
//        Node node = new Node(e);
//        node.next = head;
//        head = node;
        add(0, e);
    }

    public void addLast(E e) {
        add(size, e);
    }

    public E get(int index) {
        return getNode(index).next.e;
    }

    public void set(int index, E e) {
        getNode(index).next.e = e;
    }

    public boolean contains(E e) {
        Node curNode = dummyHead.next;
        while (curNode != null) {
            if (e.equals(curNode.e)) {
                return true;
            }
            curNode = curNode.next;
        }
        return false;
    }

    public E remove(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("非法index");
        }
        Node prevNode = getNode(index);
        Node retNode = prevNode.next;
        prevNode.next = retNode.next;
        retNode.next = null;
        size--;
        return retNode.e;
    }

    private Node getNode(int index) {
        Node prevNode = dummyHead;
        for (int i = 0; i < index; i++) {
            prevNode = prevNode.next;
        }
        return prevNode;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("LinkedList: [");
        Node curNode = dummyHead.next;
        while (curNode != null) {
            sb.append(curNode.e + "-->");
            curNode = curNode.next;
        }
        sb.append("Null]");
        return sb.toString();
    }
}

Kotlin實(shí)現(xiàn)：

//ToDo

單向鏈表的遞歸實(shí)現(xiàn)

Java實(shí)現(xiàn):

package linkedlist;

import javafx.util.Pair;

/**
 * 單向鏈表的遞歸實(shí)現(xiàn)
 *
 * @param <E> E
 * @author ZZX
 */
public class SinglyLinkedList<E> implements LinkedList<E> {
    /**
     * 節(jié)點(diǎn)內(nèi)部類
     */
    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;

    private int size;

    public SinglyLinkedList() {
        head = null;
        size = 0;
    }

    public boolean add(int index, E e) {
        if (index < 0 || index > size) {
            return false;
        }
        head = add(head, index, e);
        size++;
        return true;
    }

    private Node add(Node node, int index, E e) {
        if (0 == index) {
            return new Node(e, node);
        }
        node.next = add(node.next, index - 1, e);
        return node;
    }

    public void addFirst(E e) {
        add(0, e);
    }

    public E get(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("非法Index");
        }
        return get(head, index);
    }

    public E get(Node node, int index) {
        if (0 == index) {
            return node.e;
        }
        return get(node.next, index - 1);
    }

    public void set(int index, E e) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("非法Index");
        }
        set(head, index, e);
    }

    private void set(Node node, int index, E e) {
        if (0 == index) {
            node.e = e;
            return;
        }
        set(node.next, index - 1, e);
    }

    public E remove(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("非法Index");
        }
        Pair<Node, E> res = remove(head, index);
        return res.getValue();
    }

    private Pair<Node, E> remove(Node node, int index) {
        if (0 == index) {
            return new Pair<>(node.next, node.e);
        }
        Pair<Node, E> res = remove(node.next, index - 1);
        node.next = res.getKey();
        return new Pair<>(node, res.getValue());
    }


    public E findFirst() {
        return head.next.e;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node curNode = head;
        while (curNode != null) {
            sb.append(curNode).append("-->");
            curNode = curNode.next;
        }
        return sb.append("NULL").toString();
    }

    public static void main(String[] args) {
        SinglyLinkedList<Integer> singlyLinkedList = new SinglyLinkedList<>();
        for (int i = 0; i < 10; i++) {
            singlyLinkedList.addFirst(i);
        }
        System.out.println(singlyLinkedList);
        singlyLinkedList.remove(2);
        System.out.println(singlyLinkedList);
        singlyLinkedList.set(3, 129384);
        System.out.println(singlyLinkedList);
        System.out.println(singlyLinkedList.get(3));
    }
}

二、雙向鏈表

Java實(shí)現(xiàn)：

//ToDo

Kotlin實(shí)現(xiàn):

//TODO

三、循環(huán)鏈表

Java實(shí)現(xiàn)：

//ToDo

Kotlin實(shí)現(xiàn):

//TODO
  • Tips：Java/Kotlin鏈表接口
//Java
package linkedlist;

/**
 * 鏈表增刪改查接口
 * @author ZhuZongxing
 * @param <E> 泛型
 */
public interface LinkedList<E> {
    boolean add(int index, E e);

    E remove(int index);

    void set(int index, E e);

    E get(int index);

    int getSize();

    boolean isEmpty();
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 一、鏈表的定義 鏈表是一種遞歸的數(shù)據(jù)結(jié)構(gòu)，是一種線性結(jié)構(gòu)，但是并不會按線性的順序存儲數(shù)據(jù)，而是在每一個節(jié)點(diǎn)里存到下...
    熊喵先森閱讀 1,581評論 0贊 3
  • 基本概念 鏈表的含義： 鏈表是一種用于存儲數(shù)據(jù)集合的數(shù)據(jù)結(jié)構(gòu)，具有以下屬性 相鄰元素之間通過指針相連 最后一個元素...
    古劍誅仙閱讀 1,058評論 0贊 3
  • 鏈表（上）：如何實(shí)現(xiàn)LRU緩存淘汰算法？ 今天我們來聊聊“鏈表（Linked list）”這個數(shù)據(jù)結(jié)構(gòu)。學(xué)習(xí)鏈表有...
    GhostintheCode閱讀 1,418評論 0贊 4
  • 鏈表：數(shù)據(jù)存儲結(jié)構(gòu)我們通過一個簡單的場景，了解一下鏈表的數(shù)據(jù)存儲結(jié)構(gòu)。那就是LRU緩存淘汰算法。 緩存是一種提高數(shù)...
    初心myp閱讀 742評論 0贊 1
  • 有頭鏈表（注意：頭結(jié)點(diǎn)有的地方是全局變量） 初學(xué)者學(xué)自于大話數(shù)據(jù)結(jié)構(gòu)，不足及錯誤的地方請讀者提出來，謝謝。 可加 ...
    lxr_閱讀 981評論 0贊 2

友情鏈接更多精彩內(nèi)容