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. 头插法

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

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

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

若链表为空，同头插法；
若链表不为空，则把链表尾节点的 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("下标不合法！");
        }
    }

    /**
     * 3.任意位置插入，第一个数据节点为0号下标
     * @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位置的节点
        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 在单链表中

/**
 * 4.查找是否包含关键字 key 在单链表中
 * @param key 要查找的关键字
 * @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. 删除第一次出现关键字为 key 的节点

/**
 * 5.删除第一次出现关键字为 key 的节点
 * @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;
            // 头节点
            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 的节点

/**
 * 6.删除所有值为 key 的节点
 * @param key
 */
@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;
    }
}

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

/**
 * 9.清空顺序表以防内存泄漏
 */
@override
public 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;
    }

    /**
     * 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("下标不合法！");
        }
    }

    /**
     * 3.任意位置插入，第一个数据节点为0号下标
     * @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位置的节点
        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 在单链表中
     * @param key 要查找的关键字
     * @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.删除第一次出现关键字为 key 的节点
     * @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;
                // 头节点
                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 的节点
     * @param key
     */
    @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;
        }
    }

    /**
     * 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.清空顺序表以防内存泄漏
     */
    @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();
    }
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。