我理解的数据结构（四）—— 链表（Linked List）

Scorpion 发布于2019-08-19 11:04 / 3569人阅读

摘要：数组在末尾添加元素很简单，而链表在头部添加元素很简单。原因是数组维护者，而链表维护者。解决办法如果每次操作，不用去判断，而是直接添加就好了。我们可以增加一个虚拟头节点这个节点什么都不做，仅仅是之前的那个节点。

我理解的数据结构（四）—— 链表（Linked List） 一、链表基础

链表与数组的最大区别：链表是一种真正动态的数据结构

数据存储在“节点”中

优点：真正的动态，不需要处理固定容量的问题

缺点：丧失了随机访问的能力（索引访问）

数据存储在“节点”中

class Node {
    E e;
    Node next;
}

二、链表添加元素的原理图

链表与数组在添加元素方面有很大的不同。数组在末尾添加元素很简单，而链表在头部添加元素很简单。原因是：数组维护者size，而链表维护者head。原理如下：

三、链表添加元素代码实现

public class LinkedList {

    // 节点
    private class Node {
        // 存储的元素
        public E e;
        // 下一个节点
        public Node next;

        public Node(E e, Node node) {
            this.e = e;
            this.next = node;
        }

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

    // 练习用：在链表index位置添加一个元素e
    public void add(E e, int index) {

        if (index < 0 || index > size) {
            throw new IllegalArgumentException("index is illegal");
        }

        if (index == 0) { // 头部添加
            addFirst(e);
        } else { // 插入

            // 需要插入元素位置的上一个元素
            Node prev = head;
            for (int i = 0; i < index - 1; i++) {
                // 让prev指向插入元素的前一个元素
                prev = prev.next;
            }

//            Node node = new Node(e);
//            node.next = prev.next;
//            prev.next = node;

            // 上面三句话等价于
            prev.next = new Node(e, prev.next);

            size++;

        }

    }

    // 在链表头部添加一个元素
    public void addFirst(E e) {
//        Node node = new Node(e);
//        node.next = head;
//        head = node;

        // 上面三句话等价于
        head = new Node(e, head);

        size++;
    }

    // 在链表尾部添加元素
    public void addLast(E e) {
        add(e, size);
    }

}

四、虚拟头节点

but，有没有发现，上面的代码中有一个很不方便的地方，那就是我们每次在add操作的时候都会去做一次index是否为0的判断。

解决办法：
如果每次add操作，不用去判断，而是直接添加就好了。我们可以增加一个虚拟头节点！这个节点什么都不做，仅仅是head之前的那个节点。（是不是和循环队列我们故意浪费一个空间有点类似？）

public class LinkedList {

    // 节点
    private class Node {
        // 存储的元素
        public E e;
        // 下一个节点
        public Node next;

        public Node(E e, Node node) {
            this.e = e;
            this.next = node;
        }

        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位置添加一个元素e
    public void add(E e, int index) {

        if (index < 0 || index > size) {
            throw new IllegalArgumentException("index is illegal");
        }

        // 需要插入元素位置的上一个元素
        Node prev = dummyHead;
        for (int i = 0; i < index; i++) {
            // 让prev指向插入元素的前一个元素
            prev = prev.next;
        }

        prev.next = new Node(e, prev.next);
        size++;
    }

    // 在链表头部添加一个元素
    public void addFirst(E e) {
        add(e, 0);
    }

    // 在链表尾部添加元素
    public void addLast(E e) {
        add(e, size);
    }

}

五、链表的修改和查询操作

修改：

// 练习用：在index位置上设置元素的值为e
public void set(int index, E e) {
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("set failed, index is illegal");
    }

    Node cur = dummyHead.next;
    for (int i = 0; i < index; i++) {
        cur = cur.next;
    }
    cur.e = e;
}

// 是否包含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;
}

查询

// 练习用：获取index位置的元素
public E get(int index) {
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("get failed, index is illegal");
    }

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

@Override
public String toString() {
    StringBuilder res = new StringBuilder();

    for (Node cur = dummyHead.next; cur != null; cur = cur.next) {
        res.append(cur.e + "->");
    }
    res.append("NULL");

    return res.toString();
}

六、链表的删除操作

// 练习用：删除index位置上的元素
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 delNode = prev.next;
    prev.next = delNode.next;
    delNode.next = null;

    size--;

    return delNode.e;
}

// 删除第一个元素
public E removeFirst() {
    return remove(0);
}

// 删除最后一个元素
public E removeLast() {
    return remove(size - 1);
}

七、链表的时间复杂度分析

添加操作

addLast(e):O(n)

addFirst(e):O(1)

add(e, index):O(n/2) = O(n)

删除操作

removeLast(e):O(n)

removeFirst(e):O(1)

remove(e, index):O(n/2) = O(n)

修改操作

set(index, e):O(n)

查找操作

get(index):O(n)

contains(e):O(n)

综上：

操作	复杂度
增	O(n)
删	O(n)
改	O(n)
查	O(n)

链表的效率那么低，我们为什么还要用链表？
如果我们只对链表头部进行增、删、查操作呢？没错O(1)！这就是我们用链表的原因。

GPU云服务器云服务器对大数据的理解数据仓库的理解大数据的理解 js list 相同的数据

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/76942.html

我理解的数据结构（四）—— 链表（Linked List）

摘要：数组在末尾添加元素很简单，而链表在头部添加元素很简单。原因是数组维护者，而链表维护者。解决办法如果每次操作，不用去判断，而是直接添加就好了。我们可以增加一个虚拟头节点这个节点什么都不做，仅仅是之前的那个节点。我理解的数据结构（四）—— 链表（Linked List）一、链表基础链表与数组的最大区别：链表是一种真正动态的数据结构数据存储在节点中优点：真正的动态，不需要处理固定...

zebrayoung 2019-07-01 10:38 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0
每周一练之 数据结构与算法（LinkedList）

摘要：不同链表是链式的存储结构数组是顺序的存储结构。从列表中，移除并返回特定位置的一项。返回列表中元素个数，与数组的属性类似。提示端优先使用以上的语法实现。不要忘记在最后返回新的头引用复杂度分析时间复杂度。假设是列表的长度，时间复杂度是。这是第三周的练习题，原本应该先发第二周的，因为周末的时候，我的母亲大人来看望她的宝贝儿子，哈哈，我得带她看看厦门这座美丽的城市呀。这两天我抓紧整...

妤锋シ 2019-08-23 17:04 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月汇总（55 题攻略）

摘要：微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目录不...

warmcheng 2019-08-26 10:09 评论0 收藏0
LeetCode 160：相交链表 Intersection of Two Linked List

摘要：示例输入输出输入解释相交节点的值为注意，如果两个列表相交则不能为。解释这两个链表不相交，因此返回。注意如果两个链表没有交点，返回在返回结果后，两个链表仍须保持原有的结构。此时将指向链表长链表的头节点，不变。爱写Bug（ID：iCodeBugs）编写一个程序，找到两个单链表相交的起始节点。 Write a program to find the node at which the i...

wing324 2019-08-16 18:38 评论0 收藏0