数据结构(3)：单链表与双链表

单链表与双链表知识点

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

链表在插入的时候可以达到O(1)的复杂度，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间。它根据灵活的内存进行动态管理。

链表的类型：单向链表，双向链表以及循环链表（循环单链表、双向循环链表）。

1、单链表

代码实现：

public class LinkedListDemo {
    //定义头结点
    private Node first;
    //定义单链表中实际的数据的数目
    private int items;
    public LinkedListDemo(){
        this.first = null;
        this.items = 0;
    }
    //添加头结点
    public void addFirst(int data){
        Node node = new Node(data);
        node.next = first;
        first = node;
        items++;
    }
    //删除头结点
    public boolean delFirst(){
        if (isEmpty()){
            System.out.println("链表为空。");
            return false;
        }
        first = first.next;
        items--;
        return true;
    }
    //有序链表的插入，这样简单排序就可以用链表来实现，复杂度为O(N)
    public void add(int data){
        Node newNode = new Node(data);
        Node previous = null;
        Node current = first;
        //按从小到大的顺序排序
        while (current!=null&&data > current.data){
            previous = current;
            current = current.next;
        }
        if (previous==null){
            first = newNode;
        }else{
            previous.next = newNode;
        }
        newNode.next = current;
        items++;
    }
    //查询某个特定值的节点
    public Node findNode(int data){
        Node current = first;
        while (current!=null&&current.data!=data){
            if (current.next == null){
                System.out.println("该节点不存在。");
                return null;
            }
            current = current.next;
        }
        return current;
    }
    //删除某个特定值的节点,并返回该节点
    public Node deleteNode(int data){
        Node previous = null;
        Node current = first;//定义被删除的节点
        while (current!=null&&current.data!=data){
            if (current.next == null){
                System.out.println("该节点不存在。");
                return null;
            }
            previous = current;
            current = current.next;
        }
        if (previous==null){
            first = first.next;
        }else{
            previous.next = current.next;
        }
        items--;
        return current;
    }
    //遍历链表
    public void ergodic(){
        Node currentNode = first;
        if (currentNode==null){
            System.out.println("链表为空。");
            return;
        }
        while(currentNode!=null){
            System.out.println(currentNode.data);
            currentNode = currentNode.next;
        }
    }
    //链表的长度
    public int size(){
        return items;
    }
    //判断链表是否为空
    public boolean isEmpty(){
        return first == null;
        // return items == 0;
    }
}
class Node{
    public Node next;
    public int data;
    public Node(int data) {
        this.data = data;
    }
}

2、双链表

每个数据结点中都有两个指针，分别指向直接后继和直接前驱。

代码实现：

public class DoubleLinkedListDemo {
    private OtherNode firstNode;
    private OtherNode lastNode;
    private int size;
    public DoubleLinkedListDemo(){
        firstNode = null;
        lastNode = null;
        size = 0;
    }
    //添加头节点
    public void addFirst(int data){
        OtherNode newNode = new OtherNode(data);
        if (isEmpty()){
            lastNode = newNode;
        }else{
            firstNode.previous = newNode;
            newNode.next = firstNode;
        }
        firstNode = newNode;
        size++;
    }
    //添加尾节点
    public void addLast(int data){
        OtherNode newNode = new OtherNode(data);
        if (isEmpty()){
           firstNode = newNode;
        }else{
            lastNode.next = newNode;
            newNode.previous  = lastNode;
        }
        lastNode = newNode;
        size++;
    }
    //删除头结点,并返回头结点
    public OtherNode delFirst(){
        if (isEmpty()){
            System.out.println("链表为空。");
            return null;
        }
        OtherNode current = firstNode;
        if (size == 1){
            lastNode = null;
        }else {
            firstNode.next.previous = null;
        }
        firstNode = firstNode.next;
        size--;
        return current;
    }
    //删除尾节点，并返回尾节点
    public OtherNode delLast(){
        if (isEmpty()){
            System.out.println("链表为空。");
            return null;
        }
        OtherNode current = lastNode;
        if (size == 1){
            firstNode = null;
        }else {
            lastNode.previous.next = null;
        }
        lastNode = lastNode.previous;
        size--;
        return current;
    }
    //将节点插入到指定值为key的节点后面
    public void insertNode(int key , int data){
        OtherNode newNode = new OtherNode(data);
        OtherNode current = firstNode;
        if (isEmpty()){
            System.out.println("没有" + data + "的值。");
            return;
        }
        while (current.data !=data){
            if (current==null){
                System.out.println("没有" + data + "的值。");
                return;
            }
            current = current.next;
        }
        current.next.previous = newNode;
        newNode.next = current.next;
        current.next = newNode;
        newNode.previous = current;
        size++;
    }
    //删除特定的节点,并返回该节点
    public OtherNode delNode(int data){
        if (isEmpty()){
            System.out.println("没有" + data + "的值。");
        }
        OtherNode current = firstNode;
        while (current.data!=data){
            if (current.next == null){
                System.out.println("没有" + data + "的值。");
            }
            current = current.next;
        }
        if (current == firstNode){
            delFirst();
        }else if(current == lastNode){
            delLast();
        }else{
            current.previous.next = current.next;
            current.next.previous =  current.previous;
        }
        size--;
        return current;
    }
    //正向遍历链表
    public void ergodicForward(){
        OtherNode current = firstNode;
        while (current!=null){
            System.out.println(current.data);
            current = current.next;
        }
    }
    //反向遍历链表
    public void ergodicBackward(){
        OtherNode current = lastNode;
        while (current!=null){
            System.out.println(current.data);
            current = current.next;
        }
    }
    //判断链表是否为空
    public boolean isEmpty(){
        return size == 0;
        //return firstNode==null&&lastNode==null;
    }
    //得到链表容量
    public int size(){
        return size;
    }
}
class OtherNode{
    //指向前一个节点
    public OtherNode previous;
    //指向后一个节点
    public OtherNode next;
    //数据域
    public int data;
    public OtherNode(int data) {
        this.data = data;
    }
}

后续如有更优的方法，会继续补充。