Java如何实现无头双向链表操作

这篇文章主要介绍了Java如何实现无头双向链表操作，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。

具体内容如下

无头双向链表的结构：

代码分析

节点结构

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;  // 头节点    private Node last;  // 尾节点    public DoubleLinked() {    this.head = null;    this.last = null;}

1. 头插法

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;    }}

先判断链表是否为空，若为空，则直接插入，头节点和尾节点都直接指向新插入的元素；
若链表不为空，则把要插入节点的 next 指向链表头节点，头节点的 prev 指向新插入的节点，最后更新头节点为新插入节点，插入过程如下图所示：

2. 尾插法

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;    }}

若链表为空，同头插法；
若链表不为空，则把链表尾节点的 next 指向要插入节点，要插入节点的 prev 指向链表尾节点，最后更新尾节点为新插入节点，插入过程如下图所示：

3. 查找是否包含关键字 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("下标不合法！");        }    }        @Override    public boolean addIndex(int index, int data) {        if (index ==0) {            addFirst(data);            return true;        }        if (index == getLength()) {            addLast(data);            return true;        }        // cur 指向index位置的节点        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. 查找是否包含关键字 key 在单链表中

@Overridepublic boolean contains(int key) {    Node cur = this.head;    while (cur != null) {        if (cur.data == key) {            return true;        }        cur = cur.next;    }    return false;}

5. 删除第一次出现关键字为 key 的节点

@Overridepublic int remove(int key) {    Node cur = this.head;    int oldData = 0;    while (cur != null) {        if (cur.data == key) {            oldData = cur.data;            // 头节点            if (cur == this.head) {                this.head = this.head.next;                this.head.prev = null;            } else {                // cur.next != null --->不是尾节点                if (cur.next != null) {                    cur.next.prev = cur.prev;                } else {                    this.last = cur.prev;                }            }            return oldData;        }        cur = cur.next;    }    return -1;}

6. 删除所有值为 key 的节点

@Overridepublic void removeAllKey(int key) {    Node cur = this.head;    while (cur != null) {        if (cur.data == key) {            // 头节点            if (cur == this.head) {                this.head = this.head.next;                this.head.prev = null;            } else {                cur.prev.next = cur.next;                // cur.next != null --->不是尾节点                if (cur.next != null) {                    cur.next.prev = cur.prev;                } else {                    this.last = cur.prev;                }            }        }        cur = cur.next;    }}

7. 得到单链表的长度

@Overridepublic int getLength() {    int count = 0;    Node cur = this.head;    while (cur != null) {        count++;        cur = cur.next;    }    return count;}

8. 打印链表

@Overridepublic 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. 清空顺序表以防内存泄漏

@Overridepublic void clear() {    while(this.head != null) {        Node cur = this.head.next;        this.head.next = null;        this.head.prev = null;        this.head = cur;    }}

接口、实现方法、测试

1. 接口

package com.github.doubly;// 不带头节点单链表的实现public interface IDoubleLinked {    // 1.头插法    void addFirst(int data);    // 2.尾插法    void addLast(int data);    // 3.任意位置插入，第一个数据节点为0号下标    boolean addIndex(int index, int data);    // 4.查找是否包含关键字 key 在单链表中    boolean contains(int key);    // 5.删除第一次出现关键字为 key 的节点    int remove(int key);    // 6.删除所有值为 key 的节点    void removeAllKey(int key);    // 7.得到单链表的长度    int getLength();    // 8.打印链表    void display();    // 9.清空顺序表以防内存泄漏    void clear();}

2. 实现方法

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;  // 头节点    private Node last;  // 尾节点    public DoubleLinked() {        this.head = null;        this.last = null;    }        @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;        }    }        @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("下标不合法！");        }    }        @Override    public boolean addIndex(int index, int data) {        if (index ==0) {            addFirst(data);            return true;        }        if (index == getLength()) {            addLast(data);            return true;        }        // cur 指向index位置的节点        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;    }        @Override    public boolean contains(int key) {        Node cur = this.head;        while (cur != null) {            if (cur.data == key) {                return true;            }            cur = cur.next;        }        return false;    }        @Override    public int remove(int key) {        Node cur = this.head;        int oldData = 0;        while (cur != null) {            if (cur.data == key) {                oldData = cur.data;                // 头节点                if (cur == this.head) {                    this.head = this.head.next;                    this.head.prev = null;                } else {                    // cur.next != null --->不是尾节点                    if (cur.next != null) {                        cur.next.prev = cur.prev;                    } else {                        this.last = cur.prev;                    }                }                return oldData;            }            cur = cur.next;        }        return -1;    }        @Override    public void removeAllKey(int key) {        Node cur = this.head;        while (cur != null) {            if (cur.data == key) {                // 头节点                if (cur == this.head) {                    this.head = this.head.next;                    this.head.prev = null;                } else {                    cur.prev.next = cur.next;                    // cur.next != null --->不是尾节点                    if (cur.next != null) {                        cur.next.prev = cur.prev;                    } else {                        this.last = cur.prev;                    }                }            }            cur = cur.next;        }    }        @Override    public int getLength() {        int count = 0;        Node cur = this.head;        while (cur != null) {            count++;            cur = cur.next;        }        return count;    }        @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();    }        @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();    }}

感谢你能够认真阅读完这篇文章，希望小编分享的“Java如何实现无头双向链表操作”这篇文章对大家有帮助，同时也希望大家多多支持编程网，关注编程网行业资讯频道，更多相关知识等着你来学习!