Java数据结构之链表-双端链表

朴灿烈づ我的快乐病毒、 2022-02-13 14:49 324阅读 0赞

**链表（Linked list）**

是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

**双端链表：**

只能从一个方向遍历，相对于单向链表多了一个对尾节点的引用，这样在操作添加尾节点会方便很多；在单向链表中，添加尾节点每次都需要从头节点遍历到尾部找到尾节点再添加。

示例代码：

/**
     * Created by Administrator on 2019/4/28.
     */
    public class DoublePointLinkedList {
        private int size;//节点的个数
    
        private Node head;//头结点
    
        private Node tail;//尾节点
    
        private class Node {
            private Object data;
            private Node next;
    
            public Node(Object data) {
                this.data = data;
            }
        }
    
        public DoublePointLinkedList() {
            this.size = 0;
            this.head = null;
            this.tail = null;
        }
    
        //添加头结点
        public Node addHead(Object data) {
            Node node = new Node(data);
            if (size == 0) {//当链表为空的时候 添加节点 头结点==尾节点
                this.head = node;
                this.tail = node;
            } else {
                node.next = this.head;
                this.head = node;
            }
            this.size++;
            return node;
        }
    
        //添加尾节点
        public Node addTail(Object data) {
            Node node = new Node(data);
            this.tail.next = node;
            this.tail = node;
            this.size++;
    
            return node;
        }
    
        //是否为空
        public boolean isEmpty() {
            return this.size == 0;
        }
    
        //删除头结点
        public Node delHead() {
            Node node = this.head;
            if(node.next == null){
                this.tail = node.next;
            }
            this.head = node.next;
            this.size--;
            return node;
        }
    
        //删除尾节点
        public Node delTail() {
            Node node = this.head;
            while (null != node){
                if(null == node.next){
                    this.head = null;
                    this.tail = null;
                    return node;
                }
                if(null == node.next.next){
                    Node temp = node.next;
                    this.tail = node;
                    node.next = null;
                    return temp;
                }
                node = node.next;
            }
            this.size--;
            return node;
        }
    
        //根据节点内容查询节点
        public Node findObj(Object data) {
            Node node = this.head;
            while (null != node) {
                if (data.equals(node.data)) {
                    return node;
                }
            }
            return null;
        }
    
        //显示节点信息
        public void display() {
            Node node = this.head;
            System.out.print("[");
            while (null != node) {
                Node temp = node.next;
                if (null != temp) {
                    System.out.print(node.data + "->");
                } else {
                    System.out.print(node.data);
                }
                node = temp;
            }
            System.out.println("]");
        }
    }

测试代码：

public class Main {
    
        public static void main(String[] args) {
    //        Main.testSingleLinkedList();
            Main.testDoublePointLinkedList();
        }
    
        private static void testSingleLinkedList(){
            SingleLinkedList linkedList = new SingleLinkedList();
            linkedList.display();//打印
            linkedList.insert(null, linkedList.createNode("A"));
            linkedList.insert("A", linkedList.createNode("B"));
            linkedList.insert("B", linkedList.createNode("C"));
            linkedList.insert("C", linkedList.createNode("D"));
            linkedList.insert("D", linkedList.createNode("E"));
            linkedList.display();
            linkedList.insert("A", linkedList.createNode("A1"));
            linkedList.display();
            linkedList.delNodeByObj("A");
            linkedList.display();
        }
    
        private static void testDoublePointLinkedList(){
            DoublePointLinkedList list = new DoublePointLinkedList();
            list.display();
            list.addHead("C");
            list.addHead("B");
            list.addHead("A");
            list.display();
            list.addTail("D");
            list.addTail("E");
            list.addTail("F");
            list.display();
            list.delHead();
            list.display();
            list.delTail();
            list.display();
        }
    }

测试结果：

[]
    [A->B->C]
    [A->B->C->D->E->F]
    [B->C->D->E->F]
    [B->C->D->E]