双链表的基本操作

目录

一、双链表的设计

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

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

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

3.获取指定位置的节点

4.在尾部添加结点元素

5.在指定位置添加元素

6.删除指定位置的结点

---

一、双链表的设计

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

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

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

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

public class MyDoubleLinkedList {
    //节点类设计，设计结点内部类
    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
                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.链表中只有一个元素且在第一个元素前插入。

//在指定位置添加元素
    //思路：一共有四种情况需要考虑，
    //     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--;
    }