java实现双链表

分手后的思念是犯贱 2023-09-27 11:03 153阅读 0赞

![在这里插入图片描述][d031830ba3eb4fcc872fbd14b9adbb8d.gif_pic_center]

#### 文章目录 ####

*  一、双向链表是什么？
 *  二、具体方法实现
 *   *  定义结点
     *  下标访问异常
     *  获取链表长度
     *  打印链表
     *  清空链表
     *  头插法
     *  尾插法
     *  指定位置插入
     *  查找元素
     *  删除第一次出现的关键字
     *  删除所有值为key的节点
 *  三、完整代码

## 一、双向链表是什么？ ##

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。  
LinkedList底层就是一个双向链表，我们来实现一个双向链表。  
![示例：pandas 是基于NumPy 的一种工具，该工具是为了解决数据分析任务而创建的。][pandas _NumPy]  
这里多一个尾指针，方便我们对尾插操作从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);
        }
    }

### 获取链表长度 ###

//得到单链表的长度
        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;
        }

### 头插法 ###

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

[d031830ba3eb4fcc872fbd14b9adbb8d.gif_pic_center]: https://img-blog.csdnimg.cn/d031830ba3eb4fcc872fbd14b9adbb8d.gif#pic_center
[pandas _NumPy]: https://img-blog.csdnimg.cn/56ca5601c19546d391c72b98170e20c3.png