数据结构之链表详解

刺骨的言语ヽ痛彻心扉 2022-03-06 01:16 194阅读 0赞

### 文章目录 ###

*  链表
 *   *  链表
     *  数组和链表的对比
     *  手写一个链表
     *  为链表设立虚拟头结点
     *  链表的遍历，查询和修改
     *  链表元素的删除
     *  链表的时间复杂度分析
     *  使用链表实现栈
     *  使用链表实现队列

# 链表 #

*  动态数组、栈、队列都是底层依托静态数组，靠resize解决固定容量问题的。
 *  链表是真正的动态数据结构
 *  链表是最简单的动态数据结构

## 链表 ##

*  数据存储在“节点”（Node）中

class Node{ 
    	E e;
    	Node next;
    }

最后一个节点指向`null`（`Node.next = null`）。

> 0(head) -> 1 -> 2 -> 3 -> 4 -> null

*  优点：真正的动态，不需要处理固定容量的问题
 *  缺点：丧失了随机访问的能力

## 数组和链表的对比 ##

*  数组最好用于索引有语意的情况。scores\[2\]
 *  最大的优点：支持快速查询
 *  链表不适合用于索引有语意的情况。
 *  最大的优点：动态

## 手写一个链表 ##

/**
     * Created by binzhang on 2019/3/17.
     */
    public class LinkedList<E> { 
    
        private class Node{ 
            public E e;
            public Node next;
    
            public Node(E e, Node next){ 
                this.e = e;
                this.next = next;
            }
    
            public Node(E e){ 
                this(e, null);
            }
    
            public Node(){ 
                this(null, null);
            }
    
            @Override
            public String toString() { 
                return e.toString();
            }
        }
    
        private Node head;
        private int size;
    
        public LinkedList(){ 
            head = null;
            size = 0;
        }
    
        // 获取链表中的元素个数
        public int getSize(){ 
            return size;
        }
    
        // 返回链表是否为空
        public boolean isEmpty(){ 
            return size == 0;
        }
    
        // 在链表头添加新的元素e
        public void addFirst(E e){ 
    //        Node node = new Node(e);
    //        node.next = head;
    //        head = node;
    
            head = new Node(e, head);
            size ++;
        }
    
        // 在链表中间添加元素 关键：找到要添加的节点的前一个节点
        // 在链表的index(0-based)位置添加新的元素e
        // 在链表中不是一个常用的操作，练习用 ：）
        public void add(int index, E e){ 
            if(index < 0 || index > size)
                throw new IllegalArgumentException("Add failed. Illegal index.");
            if(index == 0){ 
                addFirst(e);
            }else{ 
                Node prev = head;
                for (int i = 0 ; i < index - 1 ; i ++)
                    prev = prev.next;
    //            Node node = new Node(e);
    //            node.next = prev.next;
    //            prev.next = node;
                prev.next = new Node(e, prev.next);
    
                size ++;
            }
        }
    
        // 在链表末尾添加新的元素e
        public void addLast(E e){ 
            add(size, e);
        }
    }

## 为链表设立虚拟头结点 ##

上面的链表代码可以看出在首部添加是和在其他位置添加有所不同的，因为其他位置的添加是对之前元素指向的修改，而头结点的添加是没有的，为了消除这个差异，我们可以为链表设立虚拟头结点，即第一个结点设置值为null，指向我们的第一个元素。

> null(dummyHead,虚拟头结点) -> 0 -> 1 -> 2 -> 3 -> 4 -> null

加入虚拟头节点后的代码：  
其实主要将`head`改为`dummyhead`即可，修改的方法只有默认的构造方法这里，和之前不同的是，初始化的长度为0的链表是存在一个内容为null的空节点的，它的作用只是为了指向我们要存入的第一个节点元素。再将之前方法中的`head`替换为`dummyHead`即可。

/**
     * Created by binzhang on 2019/3/17.
     */
    public class LinkedList<E> { 
    
        private class Node{ 
            public E e;
            public Node next;
    
            public Node(E e, Node next){ 
                this.e = e;
                this.next = next;
            }
    
            public Node(E e){ 
                this(e, null);
            }
    
            public Node(){ 
                this(null, null);
            }
    
            @Override
            public String toString() { 
                return e.toString();
            }
        }
    
        private Node dummyHead;
        private int size;
    
        public LinkedList(){ 
            dummyHead = new Node(null, null);
            size = 0;
        }
    
        // 获取链表中的元素个数
        public int getSize(){ 
            return size;
        }
    
        // 返回链表是否为空
        public boolean isEmpty(){ 
            return size == 0;
        }
    
        // 在链表中间添加元素 关键：找到要添加的节点的前一个节点
        // 在链表的index(0-based)位置添加新的元素e
        // 在链表中不是一个常用的操作，练习用 ：）
        public void add(int index, E e){ 
            if(index < 0 || index > size)
                throw new IllegalArgumentException("Add failed. Illegal index.");
    
            Node prev = dummyHead;
            for (int i = 0 ; i < index ; i ++)
                prev = prev.next;
    
            prev.next = new Node(e, prev.next);
            size ++;
    
        }
    
        // 在链表头添加新的元素e
        public void addFirst(E e){ 
            add(0, e);
        }
    
        // 在链表末尾添加新的元素e
        public void addLast(E e){ 
            add(size, e);
        }
    }

## 链表的遍历，查询和修改 ##

*  查询

// 获得链表的第index(0-based)个位置的元素
    // 在链表中不是一个常用的操作，练习用：）
    public E get(int index){ 
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Get failed. Illegal index.");
        Node cur = dummyHead.next;
        for (int i = 0 ; i < index ; i ++)
            cur = cur.next;
        return cur.e;
    }
    
    // 获得链表的第一个元素
    public E getFirst(){ 
        return get(0);
    }
    
    // 获得链表的最后一个元素
    public E getLast(){ 
        return get(size - 1);
    }

*  修改

// 修改链表的第index(0-based)个位置的元素为e
    // 在链表中不是一个常用的操作，练习用：）
    public void set(int index, E e){ 
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Set failed. Illegal index.");
        Node cur = dummyHead.next;
        for (int i = 0 ; i < index ; i ++){ 
            cur = cur.next;
        }
        cur.e = e;
    }

*  contains方法和toString方法

// 查找链表中是否有元素e
        public boolean contains(E e){ 
            Node cur = dummyHead.next;
            while (cur != null){ 
                if (cur.e.equals(e))
                    return true;
                cur = cur.next;
            }
            return false;
        }
    
        @Override
        public String toString() { 
            StringBuilder res = new StringBuilder();
    //        Node cur = dummyHead.next;
    //        while (cur != null){ 
    //            res.append(cur + " -> ");
    //            cur = cur.next;
    //        }
            for (Node cur = dummyHead.next ; cur != null ; cur = cur.next)
                res.append(cur + " -> ");
            res.append("NULL");
            return res.toString();
        }

*  测试插入功能

输出：

0 -> NULL
    1 -> 0 -> NULL
    2 -> 1 -> 0 -> NULL
    3 -> 2 -> 1 -> 0 -> NULL
    4 -> 3 -> 2 -> 1 -> 0 -> NULL
    4 -> 3 -> 666 -> 2 -> 1 -> 0 -> NULL

## 链表元素的删除 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70]  
如图要删除索引为2的元素，我们首先找到索引为1的元素，将它的next指向3，再将2节点释放即可。

// 从链表中删除index(0-based)位置的元素，返回删除的元素
    // 在链表中不是一个常用的操作，练习用：）
    public E remove(int index){ 
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed. Index is illegal.");
        Node prev = dummyHead;
        for (int i = 0 ; i < index ; i ++)
            prev = prev.next;
        Node retNode = prev.next;
        prev.next = retNode.next;
        retNode.next = null;
        size --;
    
        return retNode.e;
    }
    
    // 从链表中删除第一个元素，返回删除的元素
    public E removeFirst(){ 
        return remove(0);
    }
    
    // 从链表中删除最后一个元素，返回删除的元素
    public E removeLast(){ 
        return remove(size - 1);
    }

*  测试remove方法

public class Main { 
    
        public static void main(String[] args) { 
           LinkedList<Integer> linkedList = new LinkedList<>();
           for (int i = 0 ; i < 5 ; i ++){ 
               linkedList.addFirst(i);
                System.out.println(linkedList);
            }
    
            linkedList.add(2,666);
            System.out.println(linkedList);
    
            linkedList.remove(2);
            System.out.println(linkedList);
    
            linkedList.removeLast();
            System.out.println(linkedList);
        }
    }

输出：

0 -> NULL
    1 -> 0 -> NULL
    2 -> 1 -> 0 -> NULL
    3 -> 2 -> 1 -> 0 -> NULL
    4 -> 3 -> 2 -> 1 -> 0 -> NULL
    4 -> 3 -> 666 -> 2 -> 1 -> 0 -> NULL
    4 -> 3 -> 2 -> 1 -> 0 -> NULL
    4 -> 3 -> 2 -> 1 -> NULL

## 链表的时间复杂度分析 ##

*  **添加操作 O(n)**  
    addLast(e) O(n)  
    addFirst(e) O(1)  
    add(index,e) O(n/2)=O(n)
 *  **删除操作 O(n)**  
    removeLast(e) O(n)  
    removeFirst(e) O(1)  
    remove(index,e) O(n/2)=O(n)
 *  **修改操作 O(n)**  
    set(index,e) O(n)
 *  **查找操作 O(n)**  
    get(index) O(n)  
    contains(e) O(n)
 *  **总结**  
    链表的增删改查的时间复杂度都是O(n)  
    不过增删操作如果只对链表头进行操作时间复杂度是O(1)  
    查如果只查链表头的元素时间复杂度也是O(1)

## 使用链表实现栈 ##

Stack：

/**
     * Created by binzhang on 2019/3/18.
     */
    public interface Stack<E> { 
        int getSize();
        boolean isEmpty();
        void push(E e);
        E pop();
        E peak();
    }

LinkedListStack：

/**
     * Created by binzhang on 2019/3/18.
     */
    public class LinkedListStack<E> implements Stack<E> { 
    
        private LinkedList<E> list;
    
        public LinkedListStack(){ 
            list = new LinkedList<>();
        }
    
        @Override
        public int getSize() { 
            return list.getSize();
        }
    
        @Override
        public boolean isEmpty() { 
            return list.isEmpty();
        }
    
        @Override
        public void push(E e) { 
            list.addFirst(e);
        }
    
        @Override
        public E pop() { 
            return list.removeFirst();
        }
    
        @Override
        public E peak() { 
            return list.getFirst();
        }
    
        @Override
        public String toString() { 
            StringBuilder res = new StringBuilder();
            res.append("Stack: top ");
            res.append(list);
            return res.toString();
        }
    
        public static void main(String[] args) { 
            LinkedListStack<Integer> stack = new LinkedListStack<>();
            for (int i = 0; i < 5; i++) { 
                stack.push(i);
                System.out.println(stack);
            }
    
            stack.pop();
            System.out.println(stack);
        }
    }

输出：

Stack: top 0 -> NULL
    Stack: top 1 -> 0 -> NULL
    Stack: top 2 -> 1 -> 0 -> NULL
    Stack: top 3 -> 2 -> 1 -> 0 -> NULL
    Stack: top 4 -> 3 -> 2 -> 1 -> 0 -> NULL
    Stack: top 3 -> 2 -> 1 -> 0 -> NULL

## 使用链表实现队列 ##

我们知道链表的增删操作只有对链表头进行操作的时候时间复杂度是`O(1)`的，对链表尾操作时`O(n)`（因为要先遍历，找到这个元素再进行增删），所以链表可以适用于栈，可是用于队列时间复杂度`O(n)`是明显不适用的。所以我们要先改进我们的链表。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70 1]  
我们加入一个新的标识`tail`，`head`做队首，`tail`做队尾。  
从`head`端删除元素，从`tail`端插入元素。  
由于没有`dummyHead`，要注意链表为空的情况。  
Queue：

/**
     * Created by binzhang on 2019/3/17.
     */
    public interface Queue<E> { 
        int getSize();
        boolean isEmpty();
        void enqueue(E e);
        E dequeue();
        E getFront();
    }

LinkedListQueue：

/**
     * Created by binzhang on 2019/3/18.
     */
    public class LinkedListQueue<E> implements Queue<E> { 
    
        private class Node{ 
            public E e;
            public Node next;
    
            public Node(E e, Node next){ 
                this.e = e;
                this.next = next;
            }
    
            public Node(E e){ 
                this(e, null);
            }
    
            public Node(){ 
                this(null, null);
            }
    
            @Override
            public String toString() { 
                return e.toString();
            }
        }
    
        private Node head, tail;
        private int size;
    
        public LinkedListQueue(){ 
            head = null;
            tail = null;
            size = 0;
        }
    
        @Override
        public int getSize() { 
            return size;
        }
    
        @Override
        public boolean isEmpty() { 
            return size == 0;
        }
    
        @Override
        public void enqueue(E e) { 
            if (tail == null){ 
                tail = new Node(e);
                head = tail;
            }
            else{ 
                tail.next = new Node(e);
                tail = tail.next;
            }
            size ++;
    
        }
    
        @Override
        public E dequeue() { 
            if (isEmpty())
                throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
            Node retNode = head;
            head = head.next;
            if(head == null)
                tail = null;
            size --;
            return retNode.e;
        }
    
        @Override
        public E getFront() { 
            if (isEmpty())
                throw new IllegalArgumentException("Queue is empty");
            return head.e;
        }
    
        @Override
        public String toString() { 
            StringBuilder res = new StringBuilder();
            res.append("Queue: front ");
    
            Node cur = head;
            while (cur != null){ 
                res.append(cur + " -> ");
                cur = cur.next;
            }
            res.append("NULL tail");
            return res.toString();
        }
    
        public static void main(String[] args) { 
            LinkedListQueue<Integer> queue = new LinkedListQueue<>();
            for (int i = 0 ; i < 10 ; i ++){ 
                queue.enqueue(i);
                System.out.println(queue);
                if (i % 3 == 2){ 
                    queue.dequeue();
                    System.out.println(queue);
                }
            }
        }
    }

运行结果：

Queue: front 0 -> NULL tail
    Queue: front 0 -> 1 -> NULL tail
    Queue: front 0 -> 1 -> 2 -> NULL tail
    Queue: front 1 -> 2 -> NULL tail
    Queue: front 1 -> 2 -> 3 -> NULL tail
    Queue: front 1 -> 2 -> 3 -> 4 -> NULL tail
    Queue: front 1 -> 2 -> 3 -> 4 -> 5 -> NULL tail
    Queue: front 2 -> 3 -> 4 -> 5 -> NULL tail
    Queue: front 2 -> 3 -> 4 -> 5 -> 6 -> NULL tail
    Queue: front 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> NULL tail
    Queue: front 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> NULL tail
    Queue: front 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> NULL tail
    Queue: front 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> NULL tail

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70]: /images/20220303/11b5e958a3884b2da4d48970c245cacf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70 1]: /images/20220303/cf2c5fdde3de4ea69decadfa29315373.png