沃梦达 / 编程技术 / 编程语言 / Java开发 / 正文

Java实现双链表的示例代码

Java开发
2023-06-01

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。本文将用Java语言实现双链表，需要的可以参考一下

一、双向链表是什么

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

LinkedList底层就是一个双向链表，我们来实现一个双向链表。

这里多一个尾指针，方便我们对尾插操作从O(n)降到O(1).每个结点多了前驱结点，方便我们对链表进行操作。

二、具体方法实现

定义结点

class ListNode {
        int value;
        ListNode next;
        ListNode prev;

        public ListNode(int value) {
            this.value = value;
        }
    }

下标访问异常

public class IndexWrongException extends RuntimeException{
    public IndexWrongException() {
    }

    public IndexWrongException(String message) {
        super(message);
    }
}

获取链表长度

class ListNode {
        int value;
        ListNode next;
        ListNode prev;

        public ListNode(int value) {
            this.value = value;
        }
    }

打印链表

class ListNode {
        int value;
        ListNode next;
        ListNode prev;

        public ListNode(int value) {
            this.value = value;
        }
    }

清空链表

public void clear(){
        if(this.head == null) {
            return;
        }
        ListNode cur = this.head;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.prev = null;
            cur.next = null;
            cur = curNext;
        }
        head = null;
        tail = null;
    }

头插法

public void addFirst(int data){
        ListNode node = new ListNode(data);
        if(head == null) {
            this.head = node;
            this.tail = node;
            return;
        }
        node.next = this.head;
        this.head.prev = node;
        this.head = node;
    }

尾插法

public void addLast(int data){
        ListNode node = new ListNode(data);
        if(head == null) {
            this.head = node;
            this.tail = node;
            return;
        }
        tail.next = node;
        node.prev = tail;
        tail = node;
    }

指定位置插入

public void addIndex(int index,int data) throws IndexWrongException{
        if(index < 0 || index > size()) {
            throw new IndexWrongException("输入下标不合法");
        }
        ListNode node = new ListNode(data);
        if(index == 0) {
            addFirst(data);
            return;
        }
        if(index == size()) {
            addLast(data);
            return;
        }
        ListNode cur = this.head;
        while(index != 0) {
            cur = cur.next;
            index--;
        }
        node.next = cur;
        cur.prev.next = node;
        node.prev = cur.prev;
        cur.prev = node;
    }

查找元素

public boolean contains(int key){
        if(head == null) {
            return false;
        }
        ListNode cur = this.head;
        while(cur != null) {
            if(cur.value == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

删除第一次出现的关键字

public void remove(int key){
        ListNode cur = head;
        while(cur != head) {
            if(cur.value == key) {
                if(cur == head) {
                    head = head.next;
                    if(head.next != null) {
                        head.prev = null;
                    }else {
                        tail = null;
                    }
                }else {
                    cur.prev.next = cur.next;
                    if(cur.next != null) {
                        cur.next.prev = cur.prev;
                    }else {
                        tail = cur.prev;
                        tail.next = null;
                        }
                    }
                return;
                }
            cur = cur.next;
            }
        }

删除所有值为key的节点

public void removeAllKey(int key){
        ListNode cur = head;
        while(cur != head) {
            if(cur.value == key) {
                if(cur == head) {
                    head = head.next;
                    if(head.next != null) {
                        head.prev = null;
                    }else {
                        tail = null;
                    }
                }else {
                    cur.prev.next = cur.next;
                    if(cur.next != null) {
                        cur.next.prev = cur.prev;
                    }else {
                        tail = cur.prev;
                        tail.next = null;
                    }
                }
            }
            cur = cur.next;
        }
    }

三、完整代码

public class LinkedList {
    static class ListNode {
        int value;
        ListNode next;
        ListNode prev;

        public ListNode(int value) {
            this.value = value;
        }
    }
    ListNode head;
    ListNode tail;
    //头插法
    public void addFirst(int data){
        ListNode node = new ListNode(data);
        if(head == null) {
            this.head = node;
            this.tail = node;
            return;
        }
        node.next = this.head;
        this.head.prev = node;
        this.head = node;
    }
    //尾插法
    public void addLast(int data){
        ListNode node = new ListNode(data);
        if(head == null) {
            this.head = node;
            this.tail = node;
            return;
        }
        tail.next = node;
        node.prev = tail;
        tail = node;
    }
    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data) throws IndexWrongException{
        if(index < 0 || index > size()) {
            throw new IndexWrongException("输入下标不合法");
        }
        ListNode node = new ListNode(data);
        if(index == 0) {
            addFirst(data);
            return;
        }
        if(index == size()) {
            addLast(data);
            return;
        }
        ListNode cur = this.head;
        while(index != 0) {
            cur = cur.next;
            index--;
        }
        node.next = cur;
        cur.prev.next = node;
        node.prev = cur.prev;
        cur.prev = node;
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        if(head == null) {
            return false;
        }
        ListNode cur = this.head;
        while(cur != null) {
            if(cur.value == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key){
        ListNode cur = head;
        while(cur != head) {
            if(cur.value == key) {
                if(cur == head) {
                    head = head.next;
                    if(head.next != null) {
                        head.prev = null;
                    }else {
                        tail = null;
                    }
                }else {
                    cur.prev.next = cur.next;
                    if(cur.next != null) {
                        cur.next.prev = cur.prev;
                    }else {
                        tail = cur.prev;
                        tail.next = null;
                        }
                    }
                return;
                }
            cur = cur.next;
            }
        }
    //删除所有值为key的节点
    public void removeAllKey(int key){
        ListNode cur = head;
        while(cur != head) {
            if(cur.value == key) {
                if(cur == head) {
                    head = head.next;
                    if(head.next != null) {
                        head.prev = null;
                    }else {
                        tail = null;
                    }
                }else {
                    cur.prev.next = cur.next;
                    if(cur.next != null) {
                        cur.next.prev = cur.prev;
                    }else {
                        tail = cur.prev;
                        tail.next = null;
                    }
                }
            }
            cur = cur.next;
        }
    }
    //得到单链表的长度
    public int size(){
        ListNode cur = head;
        int count = 0;
        while(cur != null) {
            cur = cur.next;
            count++;
        }
        return count;
    }
    public void display(){
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.value+" ");
            cur = cur.next;
        }
        System.out.println();
    }
    public void clear(){
        if(this.head == null) {
            return;
        }
        ListNode cur = this.head;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.prev = null;
            cur.next = null;
            cur = curNext;
        }
        head = null;
        tail = null;
    }
}

到此这篇关于Java实现双链表的示例代码的文章就介绍到这了,更多相关Java双链表内容请搜索编程学习网以前的文章希望大家以后多多支持编程学习网！

本文标题为：Java实现双链表的示例代码

上一篇： Java设计模式之适配器模式
下一篇： Java实现新建有返回值的线程的示例详解

基础教程推荐

学习HTML
学习jQuery
学习Laravel
学习CSS3
学习Vue.js
学习Bootstrap5
学习ThinkPHP
学习AJAX
猜你喜欢
最新文章
热门文章
编程基础
热门标签
网站首页 HTML/CSS 菜单 Layui Yii2