Java如何實(shí)現(xiàn)無頭雙向鏈表操作

這篇文章主要介紹了Java如何實(shí)現(xiàn)無頭雙向鏈表操作，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

具體內(nèi)容如下

無頭雙向鏈表的結(jié)構(gòu)：

代碼分析

節(jié)點(diǎn)結(jié)構(gòu)

class Node {
    private int data;
    private Node next;
    private Node prev;

    public Node(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

    private Node head;  // 頭節(jié)點(diǎn)
    private Node last;  // 尾節(jié)點(diǎn)
    public DoubleLinked() {
    this.head = null;
    this.last = null;
}

1. 頭插法

/**
* 1.頭插法
* @param data
*/
public void addFirst(int data) {
    Node node = new Node(data);
    if (this.head == null) {
        this.head = node;
        this.last = node;
    } else {
        node.next = this.head;
        this.head.prev = node;
        this.head = node;
    }
}

先判斷鏈表是否為空，若為空，則直接插入，頭節(jié)點(diǎn)和尾節(jié)點(diǎn)都直接指向新插入的元素；
若鏈表不為空，則把要插入節(jié)點(diǎn)的 next 指向鏈表頭節(jié)點(diǎn)，頭節(jié)點(diǎn)的 prev 指向新插入的節(jié)點(diǎn)，最后更新頭節(jié)點(diǎn)為新插入節(jié)點(diǎn)，插入過程如下圖所示：

2. 尾插法

/**
* 2.尾插法
* @param data
*/
public void addLast(int data) {
    Node node = new Node(data);
    if (this.head == null) {
        this.head = node;
        this.last = node;
    } else {
        this.last.next = node;
        node.prev = this.last;
        this.last = node;
    }
}

若鏈表為空，同頭插法；
若鏈表不為空，則把鏈表尾節(jié)點(diǎn)的 next 指向要插入節(jié)點(diǎn)，要插入節(jié)點(diǎn)的 prev 指向鏈表尾節(jié)點(diǎn)，最后更新尾節(jié)點(diǎn)為新插入節(jié)點(diǎn)，插入過程如下圖所示：

3. 查找是否包含關(guān)鍵字 key 在單鏈表中

// 查找
    private Node searchIndex(int index) {
        checkIndex(index);
        int count = 0;
        Node cur = this.head;
        while (count != index) {
            cur = cur.next;
            count++;
        }
        return cur;
    }

    // 合法性檢查
    private void checkIndex(int index) {
        if (index < 0 || index > getLength()) {
            throw new IndexOutOfBoundsException("下標(biāo)不合法！");
        }
    }

    /**
     * 3.任意位置插入，第一個數(shù)據(jù)節(jié)點(diǎn)為0號下標(biāo)
     * @param index 插入位置
     * @param data 插入的值
     * @return true/false
     */
    @Override
    public boolean addIndex(int index, int data) {
        if (index ==0) {
            addFirst(data);
            return true;
        }

        if (index == getLength()) {
            addLast(data);
            return true;
        }

        // cur 指向index位置的節(jié)點(diǎn)
        Node cur = searchIndex(index);
        Node node = new Node(data);

        node.next = cur;
        cur.prev.next = node;
        node.prev = cur.prev;
        cur.prev = node;

        return true;
    }

4. 查找是否包含關(guān)鍵字 key 在單鏈表中

/**
 * 4.查找是否包含關(guān)鍵字 key 在單鏈表中
 * @param key 要查找的關(guān)鍵字
 * @return true/false
 */
@Override
public boolean contains(int key) {
    Node cur = this.head;
    while (cur != null) {
        if (cur.data == key) {
            return true;
        }
        cur = cur.next;
    }
    return false;
}

5. 刪除第一次出現(xiàn)關(guān)鍵字為 key 的節(jié)點(diǎn)

/**
 * 5.刪除第一次出現(xiàn)關(guān)鍵字為 key 的節(jié)點(diǎn)
 * @param key
 * @return
 */
@Override
public int remove(int key) {
    Node cur = this.head;
    int oldData = 0;
    while (cur != null) {
        if (cur.data == key) {
            oldData = cur.data;
            // 頭節(jié)點(diǎn)
            if (cur == this.head) {
                this.head = this.head.next;
                this.head.prev = null;
            } else {
                // cur.next != null --->不是尾節(jié)點(diǎn)
                if (cur.next != null) {
                    cur.next.prev = cur.prev;
                } else {
                    this.last = cur.prev;
                }
            }
            return oldData;
        }
        cur = cur.next;
    }
    return -1;
}

6. 刪除所有值為 key 的節(jié)點(diǎn)

/**
 * 6.刪除所有值為 key 的節(jié)點(diǎn)
 * @param key
 */
@Override
public void removeAllKey(int key) {
    Node cur = this.head;
    while (cur != null) {
        if (cur.data == key) {
            // 頭節(jié)點(diǎn)
            if (cur == this.head) {
                this.head = this.head.next;
                this.head.prev = null;
            } else {
                cur.prev.next = cur.next;
                // cur.next != null --->不是尾節(jié)點(diǎn)
                if (cur.next != null) {
                    cur.next.prev = cur.prev;
                } else {
                    this.last = cur.prev;
                }
            }
        }
        cur = cur.next;
    }
}

7. 得到單鏈表的長度

/**
 * 7.得到單鏈表的長度
 * @return
 */
@Override
public int getLength() {
    int count = 0;
    Node cur = this.head;
    while (cur != null) {
        count++;
        cur = cur.next;
    }
    return count;
}

8. 打印鏈表

/**
 * 8.打印鏈表
 */
@Override
public void display() {
    if (this.head == null) {
        return ;
    }

    Node cur = this.head;
    while (cur != null) {
        System.out.print(cur.data + " ");
        cur = cur.next;
    }

    System.out.println();
}

9. 清空順序表以防內(nèi)存泄漏

/**
 * 9.清空順序表以防內(nèi)存泄漏
 */
@Override
public void clear() {
    while(this.head != null) {
        Node cur = this.head.next;
        this.head.next = null;
        this.head.prev = null;
        this.head = cur;
    }
}

接口、實(shí)現(xiàn)方法、測試

1. 接口

package com.github.doubly;

// 不帶頭節(jié)點(diǎn)單鏈表的實(shí)現(xiàn)
public interface IDoubleLinked {
    // 1.頭插法
    void addFirst(int data);

    // 2.尾插法
    void addLast(int data);

    // 3.任意位置插入，第一個數(shù)據(jù)節(jié)點(diǎn)為0號下標(biāo)
    boolean addIndex(int index, int data);

    // 4.查找是否包含關(guān)鍵字 key 在單鏈表中
    boolean contains(int key);

    // 5.刪除第一次出現(xiàn)關(guān)鍵字為 key 的節(jié)點(diǎn)
    int remove(int key);

    // 6.刪除所有值為 key 的節(jié)點(diǎn)
    void removeAllKey(int key);

    // 7.得到單鏈表的長度
    int getLength();

    // 8.打印鏈表
    void display();

    // 9.清空順序表以防內(nèi)存泄漏
    void clear();
}

2. 實(shí)現(xiàn)方法

package com.github.doubly;

public class DoubleLinked implements IDoubleLinked {

    class Node {
        private int data;
        private Node next;
        private Node prev;

        public Node(int data) {
            this.data = data;
            this.prev = null;
            this.next = null;
        }
    }

    private Node head;  // 頭節(jié)點(diǎn)
    private Node last;  // 尾節(jié)點(diǎn)
    public DoubleLinked() {
        this.head = null;
        this.last = null;
    }

    /**
     * 1.頭插法
     * @param data
     */
    @Override
    public void addFirst(int data) {
        Node node = new Node(data);
        if (this.head == null) {
            this.head = node;
            this.last = node;
        } else {
            node.next = this.head;
            this.head.prev = node;
            this.head = node;
        }
    }

    /**
     * 2.尾插法
     * @param data
     */
    @Override
    public void addLast(int data) {
        Node node = new Node(data);
        if (this.head == null) {
            this.head = node;
            this.last = node;
        } else {
            this.last.next = node;
            node.prev = this.last;
            this.last = node;
        }
    }

    // 查找
    private Node searchIndex(int index) {
        checkIndex(index);
        int count = 0;
        Node cur = this.head;
        while (count != index) {
            cur = cur.next;
            count++;
        }
        return cur;
    }

    // 合法性檢查
    private void checkIndex(int index) {
        if (index < 0 || index > getLength()) {
            throw new IndexOutOfBoundsException("下標(biāo)不合法！");
        }
    }

    /**
     * 3.任意位置插入，第一個數(shù)據(jù)節(jié)點(diǎn)為0號下標(biāo)
     * @param index 插入位置
     * @param data 插入的值
     * @return true/false
     */
    @Override
    public boolean addIndex(int index, int data) {
        if (index ==0) {
            addFirst(data);
            return true;
        }

        if (index == getLength()) {
            addLast(data);
            return true;
        }

        // cur 指向index位置的節(jié)點(diǎn)
        Node cur = searchIndex(index);
        Node node = new Node(data);

        node.next = cur;
        cur.prev.next = node;
        node.prev = cur.prev;
        cur.prev = node;

        return true;
    }

    /**
     * 4.查找是否包含關(guān)鍵字 key 在單鏈表中
     * @param key 要查找的關(guān)鍵字
     * @return true/false
     */
    @Override
    public boolean contains(int key) {
        Node cur = this.head;
        while (cur != null) {
            if (cur.data == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    /**
     * 5.刪除第一次出現(xiàn)關(guān)鍵字為 key 的節(jié)點(diǎn)
     * @param key
     * @return
     */
    @Override
    public int remove(int key) {
        Node cur = this.head;
        int oldData = 0;
        while (cur != null) {
            if (cur.data == key) {
                oldData = cur.data;
                // 頭節(jié)點(diǎn)
                if (cur == this.head) {
                    this.head = this.head.next;
                    this.head.prev = null;
                } else {
                    // cur.next != null --->不是尾節(jié)點(diǎn)
                    if (cur.next != null) {
                        cur.next.prev = cur.prev;
                    } else {
                        this.last = cur.prev;
                    }
                }

                return oldData;
            }
            cur = cur.next;
        }
        return -1;
    }

    /**
     * 6.刪除所有值為 key 的節(jié)點(diǎn)
     * @param key
     */
    @Override
    public void removeAllKey(int key) {
        Node cur = this.head;
        while (cur != null) {
            if (cur.data == key) {
                // 頭節(jié)點(diǎn)
                if (cur == this.head) {
                    this.head = this.head.next;
                    this.head.prev = null;
                } else {
                    cur.prev.next = cur.next;
                    // cur.next != null --->不是尾節(jié)點(diǎn)
                    if (cur.next != null) {
                        cur.next.prev = cur.prev;
                    } else {
                        this.last = cur.prev;
                    }
                }
            }
            cur = cur.next;
        }
    }

    /**
     * 7.得到單鏈表的長度
     * @return
     */
    @Override
    public int getLength() {
        int count = 0;
        Node cur = this.head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    /**
     * 8.打印鏈表
     */
    @Override
    public void display() {
        if (this.head == null) {
            return ;
        }

        Node cur = this.head;
        while (cur != null) {
            System.out.print(cur.data + " ");
            cur = cur.next;
        }

        System.out.println();
    }

    /**
     * 9.清空順序表以防內(nèi)存泄漏
     */
    @Override
    public void clear() {
        while(this.head != null) {
            Node cur = this.head.next;
            this.head.next = null;
            this.head.prev = null;
            this.head = cur;
        }
    }
}

3. 測試

package com.github.doubly;

public class TestDemo {
    public static void main(String[] args) {
        DoubleLinked doubleLinked = new DoubleLinked();
        doubleLinked.addFirst(10);
        doubleLinked.addFirst(20);
        doubleLinked.addFirst(30);
        doubleLinked.addFirst(40);
        doubleLinked.addFirst(50);
        doubleLinked.display();


        doubleLinked.addIndex(0,100);
        doubleLinked.addIndex(1,200);
        doubleLinked.addIndex(0,300);
        doubleLinked.addLast(40);
        doubleLinked.addLast(50);
        doubleLinked.display();

        doubleLinked.remove(300);
        doubleLinked.display();

        doubleLinked.removeAllKey(50);
        doubleLinked.display();
    }
}

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“Java如何實(shí)現(xiàn)無頭雙向鏈表操作”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關(guān)注億速云行業(yè)資訊頻道，更多相關(guān)知識等著你來學(xué)習(xí)!