数据结构之双向链表

￡神魔★判官ぃ 2022-06-18 08:08 219阅读 0赞

双向链表，每个节点除了保存了对下一个节点的引用，同时还保存这对前一个节点的引用。  
其结点跟单链表相似，如图所示：  
![这里写图片描述][SouthEast]

设计双向链表的操作：  
1、结点数据：

/** * 链表节点，相当于火车的车厢 * @author Administrator * */
    public class MyNode { 
    
        //数据域
        public  long data;
    
        //指针域
        public  MyNode next;
    
        /** * 前指针域 */
        public MyNode previous;
    
        /** * 创建节点，数据域赋值 * @param value */
        public MyNode(long value){
            this.data=value;
        }
    
        public void display(){
            System.err.print(data+" ");
        }
    }

双向链表类：

/** * 双向链表，每个节点除了保存了对下一个节点的引用，同时还保存这对前一个节点的引用 * @author Administrator * */
    public class MyDoubleLink { 
    
        /** * 头结点 */
        private MyNode first;
    
        private MyNode last;
    
        /** * 构造方法 */
        public MyDoubleLink(){
            first=null;
            last=null;
        }
    }

2、在尾部追加结点：

/** * 插入结点，从尾结点插入, * @param value */
        public void insertLast(long value){
            MyNode node=new MyNode(value);
            if (isEmpty()) {
                first=node;//若链表为空，则设置头结点为新增节点
            }else {
                last.next=node;//若链表不为空，则设置尾结点的下一个节点为新增结点,同时设置新增加的节点的前指针指向为尾结点
                node.previous=last;
            }
            last=node;
        }

3、在头部插入节点：

/** * 在头结点后插入节点，如果为空，则设置新增节点为尾结点，如果不为空，还需要设置头结点的前一个节点为新增结点 * @param value */
        public void insetFirst(long value){
            MyNode node=new MyNode(value);
            if (isEmpty()) {
                last=node;
            }else{
                first.previous=node;
            }
            node.next=first;
            first=node;
        }

4、根据关键字查询结点：

/** * 查找方法 * @param value * @return */
        public MyNode find(long value){
            MyNode currNode=first;
            while(currNode!=null){
                if (currNode.data==value) {
                    return currNode;
                }
                currNode=currNode.next;
            }
            return null;
        }

5、在结点中间的某一个位置插入节点：

/** * 在关键字之后插入结点 * @param value * @param key */
        public void insertFindByKey(long value,long key){
            MyNode curNode=find(key);
            if (curNode==null) {
                System.out.println("未找到插入结点的位置");
            }else {
                MyNode node=new MyNode(value);//要插入的结点
                node.previous=curNode;
                node.next=curNode.next;
                node.previous.next=node;
                node.next.previous=node;
            }
        }

6、删除结点  
（1）、删除头结点后的节点,从头部开始删除

/** * 删除头结点后的节点,从头部开始删除 * @return */
        public MyNode deleteFirst(){
            MyNode temp=first;//头结点
            if (first.next==null) {
                last=null;
            }else {
                first.next.previous=null;
            }
            first=temp.next;
            return temp;
        }

（2）、删除结点，从尾结点删除

/** * 删除结点，从尾结点删除 * 如果头结点后没有其他结点，则设置头结点为null。 * 否则设置尾结点的前一个结点的next为null。 * 设置尾结点为其前一个结点。 * @return */
        public MyNode deleteLast(){
            MyNode temp=last;
            if (first.next==null) {
                first=null;
            }else {
                last.previous.next=null;
            }
            last=last.previous;//将last的前一个节点设置为尾结点。
            return temp;
        }

（3）、根据关键字删除结点

/** * 删除 * @param value * @return */
        public MyNode delete(long value){
            MyNode currNode=first;
            while(currNode.data!=value){
                if (currNode.next==null) {
                    return null;
                }
                currNode=currNode.next;
            }
            if (currNode==first) {
                first=first.next;
            }else {
                currNode.previous.next=currNode.next;
            }
            return currNode;
        }

7、显示所有结点：

/** * 显示结点 */
        public void display(){
            MyNode currNode=first;
            while(currNode!=null){
                currNode.display();
                currNode=currNode.next;
            }
        }

8、判断链表是否为空

/** * 判断是否为空 * @return */
        public boolean isEmpty(){
            return first==null;
        }

[SouthEast]: /images/20220618/285025b3d76b401290c7a9cd3ac74ca9.png