双链表的基本操作

待我称王封你为后i 2023-09-24 14:18 70阅读 0赞

**目录**

一、双链表的设计

二、双链表的实现和基本操作

1.实现双链表节点以及设置first、last指针

2.获取当前链表中元素的数量

3.获取指定位置的节点

4.在尾部添加结点元素

5.在指定位置添加元素

6.删除指定位置的结点

--------------------

## 一、双链表的设计 ##

![a474dcce51684ed89452fa729ca9f30c.png][]

针对于查询操作，我们可以从前往后遍历，也可从后往前遍历。

## 二、双链表的实现和基本操作 ##

### **1.实现双链表节点以及设置first、last指针** ###

>     //注意：这里的first和last节点，跟单链表中的头结点不一样，
>     //     头结点是专门的一个节点指向链表第一个结点
>     //     而这里的first和last节点相当于指针一样，指向第一个和最后一个节点

![9a771964a9be4db38aedfe76b5885c18.png][]

public class MyDoubleLinkedList<T> {
        //节点类设计，设计结点内部类
        public class Node{
            //存储数据的变量
            T item;
            //指向上一个节点的引用
            Node prev;
            //指向下一个结点的引用
            Node next;
    
            public Node(Node prev,T item, Node next) {
                this.item = item;
                this.prev = prev;
                this.next = next;
            }
        }
    
        //注意：这里的first和last节点，跟单链表中的头结点不一样，
        //     头结点是专门的一个节点指向链表第一个结点
        //     而这里的first和last节点相当于指针一样，指向第一个和最后一个节点
    
        //声明第一个结点
        Node first;
        //声明最后的结点
        Node last;
        //定义链表的长度
        int size;
        //构造方法初始化size
    
        public MyDoubleLinkedList() {
            size = 0;
        }

### **2.获取当前链表中元素的数量** ###

//获取当前存储元素的数量
        public int size(){
            return this.size;
        }

### **3.获取指定位置的节点** ###

//根据位置获取元素
        public Node getNode(int pos){
            int middle = this.size/2;
            Node x;
    
            if (pos < middle){//如果目标结点在前半部分，则从前面开始遍历
                x = first;
                for (int i = 0;i<pos;i++){
                    x = x.next;
                }
            }else {//如果目标结点在后半部分，则从后面开始遍历
                x = last;
                for (int i = size-1;i>pos;i--){
                    x = x.prev;
                }
            }
            return x;
        }

### **4.在尾部添加结点元素** ###

>     思路：将需要插入的结点前指针指向last（链表中最后一个节点），
>     //     再将last的next指针指向需要插入的结点，
>     //     最后将last游标移动到新插入的结点（即最后一个节点），将最后一个节点赋值给last。

//在尾部添加元素
        //思路：将需要插入的结点前指针指向last（链表中最后一个节点），
        //     再将last的next指针指向需要插入的结点，
        //     最后将last游标移动到新插入的结点（即最后一个节点），将最后一个节点赋值给last。
        public void add(T t){
            //将last存储在prev结点，last为链表最后一个节点
            Node prev = last;
            //创建需要插入的结点，同时将节点前指针指向last
            Node node = new Node(prev,t,null);
            //将prev的next指向新插入的结点
            //如果last为空，则链表中没有节点元素，为插入的第一个结点，
            // 将first、last游标都指向插入的第一个结点
            if (prev == null){
                first = node;
            }else {
                prev.next = node;
            }
            //将last游标指向新插入的结点
            last = node;
            //链表长度加一
            this.size++;
        }

### 5.在指定位置添加元素 ###

>     思路：一共有四种情况需要考虑，
>     //     1.在链表尾部插入节点    2.在链表中正常插入节点
>     //     3.链表中没有元素       4.链表中只有一个元素且在第一个元素前插入。

![9b736bc42a02496c90764161fc282d4a.png][]

//在指定位置添加元素
        //思路：一共有四种情况需要考虑，
        //     1.在链表尾部插入节点    2.在链表中正常插入节点
        //     3.链表中没有元素       4.链表中只有一个元素且在第一个元素前插入。
        public void add(int pos,T t){
            if (pos == size){//如果在尾部插入节点，则调用尾部插入节点方法
                add(t);
            }else {//否则不在尾部插入，在链表中或链表第一个位置插入
                //将需要插入的元素创建成节点
                Node node = new Node(null,t,null);
                //获取当前要插入节点的位置
                Node current = this.getNode(pos);
                if (current == null){
                    //链表没有元素的时候
                    first = node;
                }else {
                    //获取插入节点的前一个位置结点
                    Node prev = current.prev;
                    //将node的prev设置成prev节点
                    node.prev = prev;
                    //将node的next节点设置成current节点
                    node.next = current;
                    //将current的prev设置成node
                    current.prev = node;
                    if (prev == null){//如果链表中只有一个节点
                        //将first指向插入的元素
                        first = node;
                    }else {
                        //将prev的next设置成node
                        prev.next = node;
                    }
                }
            }
            //链表长度加一
            this.size++;
        }

### 6.删除指定位置的结点 ###

>     思路：分三种情况：
>     //     1.在链表中的正常位置删除结点
>     //     2.删除链表中第一个结点
>     //     3.删除链表中最后一个节点

//指定位置的删除功能
        //思路：分三种情况：
        //     1.在链表中的正常位置删除结点
        //     2.删除链表中第一个结点
        //     3.删除链表中最后一个节点
        public void remove(int pos){
            //获取当前需要删除的结点
            Node node = this.getNode(pos);
            //获取前一个结点
            Node prev = node.prev;
            //获取下一个节点
            Node next = node.next;
    
            //删除元素，将前一个结点与后一个节点相连
            if (prev == null){//如果需要删除的结点是第一个结点
                //将first节点指向next
                first = next;
            }else {
                prev.next = next;
            }
            if (next == null){//如果删除的结点是最后一个节点
                //将last节点指向prev
                last = prev;
            }else {
                next.prev = prev;
            }
            //链表长度减一
            this.size--;
        }

[a474dcce51684ed89452fa729ca9f30c.png]: https://img-blog.csdnimg.cn/a474dcce51684ed89452fa729ca9f30c.png
[9a771964a9be4db38aedfe76b5885c18.png]: https://img-blog.csdnimg.cn/9a771964a9be4db38aedfe76b5885c18.png
[9b736bc42a02496c90764161fc282d4a.png]: https://img-blog.csdnimg.cn/9b736bc42a02496c90764161fc282d4a.png