Java数据结构——双向链表

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

class DBNode{
     int data;//存放的数据
     DBNode next;//下一个结点
     DBNode pre;//前一个结点
     public DBNode(int data) {
           this.data = data;
     }
}

2.链表的常见操作（遍历，添加，修改，删除）

1. 遍历 和单链表一样，只是可以向前，也可以向后
2. 添加（默认添加到双向链表的最后）

•  先找到双向链表的最后结点
• temp.next = newHeroNode
• newHeroNode.pre = temp

        3.修改 和单向链表一样         4.删除

•  因为是双向链表，可以实现自我删除
• 直接找到要删除的这个结点，比如temp
• temp.pre.next = temp.next;
• temp.next.pre = temp.pre

代码实现：

package org.learn.link;

public class DoubleLink {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        DBlinkList mylist = new DBlinkList();
        mylist.addDBNode(1);
        mylist.addDBNode(2);
        mylist.addDBNode(3);
        mylist.addDBNode(4);
        
        System.out.println("双向链表：");
        mylist.print();
        
        System.out.println("删除后的双向链表：");
        mylist.delete(3);
        mylist.print();
    }

}

class DBlinkList{
    //头节点
    DBNode head = new DBNode(0);
    
    //添加结点到双向链表（尾部添加）
    public void addDBNode(int data) {
        DBNode newNode = new DBNode(data);
        DBNode cur = head;
        while(cur.next != null) 
            cur = cur.next;
        cur.next = newNode;
        newNode.pre = cur;
    }
    
    //删除结点
    public void delete(int data) {
        if(head.next == null) {
            System.out.println("链表为空。");
            return;
        }
        DBNode cur = head.next;
        boolean flag = false;//标志是否找到待删除结点
        while(true) {
            if(cur == null)
                break;//已经遍历完这个链表
            if(cur.data == data) {
                flag = true;
                break;
            }
            cur = cur.next;//后移
        }
        if(flag) {
            cur.pre.next = cur.next;
            if(cur.next != null)
                cur.next.pre = cur.pre;
        }else
            System.out.printf("要删除的结点数据为%d不存在\n",data);
    }
    
    //显示结点
    public void print() {
        DBNode cur = head.next;
        while(cur !=null) {
            System.out.print(cur.data+" ");
            cur = cur.next;
        }
        System.out.println();
    }
}

class DBNode{
    int data;
    DBNode next;//下一个结点
    DBNode pre;//前一个结点
    public DBNode(int data) {
        this.data = data;
    }
}

 （Ps:该篇整理在学习尚硅谷的数据结构视频后，所以，里面大部分内容都是借鉴视频内容，只是单纯记录整理，帮助自己复习回顾）