Java实现双向链表

什么是双向链表

双向链表就是每个节点都有它的前驱和后置节点指针，Java中没有指针的概念，可以使用对象地址来表示。

Java实现双向链表

从上图可以看出首节点前驱指向null，尾节点的后置指向null。

双向链表中我们需要定义个节点node对象，它包含前驱和后置节点，如下：

 private static class Node{
         Integer data;//data
         Node prev ;//前驱
         Node next;//后置

        public Node(Integer data) {
            this.data = data;
        }
    }

然后再定义我们的链表类LinkedList，它包含新增节点、删除节点和显示节点三个方法。

public void show();//显示
public void add(Integer data)//添加节点
public void del(Integer data);//删除节点

这里为了理解双向列表，节点data的定义为简单的Integer类型。完整代码如下：

/**
 * Java实现双向链表
 */
class LinkedList{
    private Node head = new Node(0); //头部节点
    //定义内部类节点Node
    private static class Node{
         Integer data;//data
         Node prev ;//前驱
         Node next;//后置

        public Node(Integer data) {
            this.data = data;
        }
    }

    /**
     * show
     */
    public void show(){
        Node temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            System.out.println(temp.next.data);
            temp = temp.next;
        }
    }

    /**
     * 添加元素
     * @param data
     */
    public void add(Integer data){
        Node node = new Node(data);
        Node temp = this.head;
        while(true){
            if(temp.next == null){
                break;
            }
            //找到链表的尾部
            temp = temp.next;
        }
        temp.next = node;
        node.prev = temp;
    }

    /**
     * 删除元素
     * @param data
     */
    public void del(Integer data){
        Node temp = this.head;
        while(true){
            //向下继续找
            temp = temp.next;
            if (head.next == null) {
                System.out.println("空链表");
                break;
            }
            if (null == temp) {
                System.out.println("节点不存在");
            }
            //找当相等的元素
            if(temp.data == data){
                //当前节点的前驱指向当前节点的后置
                temp.prev.next = temp.next;
                temp.next.prev = temp.prev;
                break;
            }
        }
    }

}

public class HelloWorld{

    public static void main(String args[]){

        LinkedList list = new LinkedList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.del(2);
        list.show();

    }

}

测试一下

在上面的代码中，我们在双向链表中添加了1，2，3并删除了2。

结果输出如下：

1
3

双向链表特点

从上面的代码中我们可以看到它有如下特点：

1、可以使用一个head和一个tail分别指向头部和尾部的节点
2、每个节点都由三部分组成Data，prev，next
3、双向链表的第一个节点的prev是null
4、双向链表的最后节点的next是null