算法学习之链表

桃扇骨 2022-05-14 11:37 201阅读 0赞

# \# 算法学习之链表 #

# 一、基础知识 #

### 0x1 为什么链表很重要 ###

*  链表——真正的动态数据结构
 *  最简单的动态数据结构
 *  更深入的理解引用(或者指针)
 *  更深入的理解递归
 *  辅助组成其他数据结构

### 0x2 链表 ###

*  数据存储在“节点”中  
    ![20180906190902.png][]
 *  优点:真正的动态，不需要处理固定容量的问题
 *  缺点:丧失了随机访问的能力

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

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

# 二、链表的实现 #

### 0x1 链表的代码实现 ###

### 0x2 链表的操作 ###

1、插入链表  
![20180906193953.png][]  
关键：找到要添加的节点的前一个节点  
![20180906194717.png][]

2、其他操作

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);
        }
    }

### 0x3 虚拟链表 ###

头部有一个节点，节点值为NULL，指向第一个真实的节点。  
![20180907103725.png][]

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();
            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);
        }
    }

### 0x4 链表元素的删除 ###

删除索引为2位置的元素  
![20180907104607.png][]

// 从链表中删除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);
    }

### 0x5 链表操作的时间复杂度分析 ###

添加操作 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)  
不能随机访问

# 三、链表与递归 #

### 0x1 LeetCode上的一题的探究 ###

删除链表中等于给定值 val 的所有节点。  
示例:

输入: 1->2->6->3->4->5->6, val = 6
    输出: 1->2->3->4->5

由于是删除所有相同值的节点，需要循环。

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
        
    
        public ListNode removeElements(ListNode head, int val) {
    
            while(head != null && head.val == val){
                ListNode delNode = head;
                head = head.next;
                delNode.next = null;
            }
    
            if(head == null)
                return head;
    
            ListNode prev = head;
            while(prev.next != null){
                if(prev.next.val == val) {
                    ListNode delNode = prev.next;
                    prev.next = delNode.next;
                    delNode.next = null;
                }
                else
                    prev = prev.next;
            }
    
            return head;
        }
    }

由于是LeetCode关注算法，不用关注内存的回收。简化版：

class Solution2 {
    
        public ListNode removeElements(ListNode head, int val) {
    
            while(head != null && head.val == val)
                head = head.next;
    
            if(head == null)
                return head;
    
            ListNode prev = head;
            while(prev.next != null){
                if(prev.next.val == val)
                    prev.next = prev.next.next;
                else
                    prev = prev.next;
            }
            return head;
        }
    }

利用虚拟头节点，可以不用判断链表的头是不是需要删除的节点

class Solution3 {
    
        public ListNode removeElements(ListNode head, int val) {
    
            ListNode dummyHead = new ListNode(-1);
            dummyHead.next = head;
    
            ListNode prev = dummyHead;
            while(prev.next != null){
                if(prev.next.val == val)
                    prev.next = prev.next.next;
                else
                    prev = prev.next;
            }
            return dummyHead.next;
        }
    }

[20180906190902.png]: /images/20220514/63fda6ceeca9408c8cb095345e633716.png
[20180906193953.png]: /images/20220514/0949100a1d374b7ab5945ee352d9d7b0.png
[20180906194717.png]: /images/20220514/fe7f826e42784651b3db06d681770366.png
[20180907103725.png]: /images/20220514/a27413dafb95488fafbf01e4986474f3.png
[20180907104607.png]: /images/20220514/b1372383bf2e45b9b4030dae598eb18c.png