DS04:链表

链表

特点

链表是一个物理存储结构非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现，其示意图如下：

数据存储在节点（Node）中，主要模型如下：包括该节点存储的元素以及下一个节点的地址。

class Node {
	E e;
	Node next;
}

与顺序表的对比

1、顺序表

优点：

a、空间利用率高。因为是连续存放，所以如果查找一个元素速度很快。

b、存取速度快，通过下标来直接存储。

缺点：

a、插入/删除比较麻烦。插入或者删除的时候，整个表需要遍历挪动元素来实现。

b、空间有限制。因为数组长度是固定的，当需要存取的元素个数多于顺序表的个数时，就会出现溢出问题，而当元素个数远远小于当初分配的空间时，又会造成空间的浪费（动态数组进行扩容同样消耗大量运算）。

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

    private Node dummyHead;	// 哑节点，指向链表头节点
    int size;

    public LinkedList() {
        dummyHead = new Node(null, null);
        size = 0;
    }

插入元素

时间复杂度为O(n)。

// 在链表中间添加元素
public void add(int index, E e) {
    if(index < 0 || index > size) {
        throw new IllegalArgumentException("Add failed");
    }
    Node prev = dummyHead;
    for (int i=0;i<index;i++) {
        prev = prev.next;
    }
    prev.next = new Node(e, prev.next);
    size++;
}

删除元素

时间复杂度为O(n)

// 删除索引为index的元素
public E remove(int index) {
    if(index < 0 || index > size) {
        throw new IllegalArgumentException("Add failed");
        }
    Node prev = dummyHead;
    for (int i=0;i<index;i++) {
        prev = prev.next;
    }
    Node res = prev.next;
    prev.next = res.next;
    res.next = null;
    size--;
    return res.e;
}

还有其他的一些诸如查找、修改等方法，均只需要通过遍历链表即可实现。

同时需要注意，在头部处不管插入还是删除元素都是O(1)级别。因此使用链表作为底层结构实现栈和队列是很优越的，这在之前已经提过了。

改进方案（跳表）

由于链表的插入与查找元素等操作基本都需要对链表进行遍历操作，时间复杂度较高，所以可以有如下改进思路：

跳表是基于链表实现的有序列表，跳表通过维护一个多层级的链表实现了快速查询效果将平均时间复杂度降到了 O(logn) ，是一个典型的用空间换时间数据结构

参考：https://www.cnblogs.com/Laymen/p/14084664.html

Donate