数据结构-链表

发表于 分类于
本文字数： 4.7k 阅读时长 ≈ 4 分钟

概述

链表 是采用链式存储结构表示和实现的线性表。本文仅探讨双向链表。

其结构图大致如下：

图一：链表

链表的优缺点：

  • 优点
    • 快速实现插入、删除元素。
  • 缺点
    • 需额外空间保存元素间逻辑关系。
    • 查询效率低。

结构

链表采用链式存储结构实现，故而需要首先定义结点结构。我们采用 Java 库相同的做法，将结点定义为链表类中的一个静态类。

另外依据 Java库中 LinkedList 类的定义，可以发现它同样实现了双端队列 Deque，在此我们也这样做。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class LinkedList<E> {
    // 节点结构
    private static class Node<E> {
        // 具体元素
        E item;
        // 前驱
        Node<E> prev;
        // 后继
        Node<E> next;

        Node(Node<E> prev, E item, Node<E> next) {
            this.prev = prev;
            this.item = item;
            this.next = next;
        }
    }
    // 头结点
    private Node<E> first;
    // 尾结点
    private Node<E> last;
    // 元素个数
    private int size;
}

实现

链表往往具有两种写法——一种具有标记结点，一种不具有标记结点。

使用前者，可无需考虑一些特殊情况，但是需要耗费一个结点的空间。

Java 库采用后者，故而我们亦采用后者。

辅助方法

  • 链接元素于首部

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    private void linkFirst(E e) {
        final Node<E> first = this.first;
        final Node<E> newNode = new Node<>(null, e, first);
        if (null == first) {
            this.last = newNode;
        } else {
            first.prev = newNode;
        }
        this.first = newNode;
        this.size = this.size + 1;
    }

  • 链接元素于尾部

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    private void linkLast(E e) {
        final Node<E> last = this.last;
        final Node<E> newNode = new Node<>(last, e, null);
        if (null == last) {
            this.first = newNode;
        } else {
            last.next = newNode;
        }
        this.last = newNode;
        this.size = this.size + 1;
    }

  • 链接元素于某结点之前(结点一定存在)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    private void linkBefore(E e, Node<E> succ) {
        final Node<E> prev = succ.prev;
        final Node<E> newNode = new Node<>(prev, e, succ);
        succ.prev = newNode;
        if (null == prev) {
            this.first = newNode;
        } else {
            prev.next = newNode;
        }
        this.size = this.size + 1;
    }

  • 删除某元素(元素一定存在)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    private E unlink(Node<E> x) {
        final Node<E> prev = x.prev;
        final Node<E> next = x.next;
        E element = x.item;
        x.prev = null;
        x.item = null;
        x.next = null;

        if (null == prev) {
            this.first = next;
        } else {
            prev.next = next;
        }

        if (null == next) {
            this.last = prev;
        } else {
            next.prev = prev;
        }
        this.size = this.size - 1;
        return element;
    }

  • 查找指定位置结点

    查询指定位置结点，在此做一简单优化。如果位置位于链表前半部分，则顺序查找；否则逆向查找。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    private Node<E> node(int index) {
        if (index < (this.size >> 1)) {
            Node<E> x = this.first;
            for (int i = 0; i < index; i++) {
                x = x.next;
            }
            return x;
        } else {
            Node<E> x = this.last;
            for (int i = this.size - 1; i > index; i--) {
                x = x.prev;
            }
            return x;
        }
    }

    初始化

  • 空初始化

    1
    2
    3
    public LinkedList() {

    }

    查询

  • 查询元素个数

    1
    2
    3
    public int size() {
        return this.size;
    }

  • 查询链首

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    // Dequeu中二者是有差别的。如果链表为空，前者返回一个异常，后者返回null。对此我做了简化。
    public E getFirst() {
        final Node<E> e = this.first;
        if (null == e) {
            return null;
        }
        return e.item;
    }

    public E peekFirst() {
        return getFirst();
    }

  • 查询链尾

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    // 同上
    public E getLast() {
        final Node<E> e = this.last;
        if (null == e) {
            return null;
        }
        return e.item;
    }

    public E peekLast() {
        return getLast();
    }

  • 查询指定位置元素

    1
    2
    3
    4
    5
    6
    public E get(int index) {
        if (index < 0 || index >= this.size) {
            return null;
        }
        return node(index).item;
    }

  • 查询元素位置

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    public int indexOf(Object o) {
        if (null == o) {
            Node<E> x = this.first;
            for (int i = 0; i < this.size; i++) {
                if (null == x.item) {
                    return i;
                }
                x = x.next;
            }
        } else {
            Node<E> x = this.first;
            for (int i = 0; i < this.size; i++) {
                if (x.item.equals(o)) {
                    return i;
                }
                x = x.next;
            }
        }
        return -1;
    }

    操纵

  • 链首添加元素

    1
    2
    3
    4
    5
    6
    7
    8
    9
    // Dequeu中二者是有差别的。如果因空间限制而添加失败，前者返回一个异常，后者返回false。对此我做了简化。
    public void addFirst(E e) {
        linkFirst(e);
    }

    public boolean offerFirst(E e) {
        linkFirst(e);
        return true;
    }

  • 链尾添加元素

    1
    2
    3
    4
    5
    6
    7
    8
    9
    // 同上
    public void addLast(E e) {
        linkLast(e);
    }

    public boolean offerLast(E e) {
        linkLast(e);
        return true;
    }

  • 指定位置添加元素

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    public void add(int index, E element) {
        if (index < 0 || index > this.size) {
            return ;
        }
        if (index == this.size) {
            linkLast(element);
        } else {
            linkBefore(element, node(index));
        }
    }

  • 链首删除元素

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    // Dequeu中二者是有差别的。如果链表为空，前者返回一个异常，后者返回null。对此我做了简化。
    public E removeFirst() {
        final Node<E> f = this.first;
        if (null == f) {
            return null;
        }
        return unlink(f);
    }

    public E pollFirst() {
        return removeFirst();
    }

  • 链尾删除元素

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    // 同上
    public E removeLast() {
        final Node<E> l = this.last;
        if (null == l) {
            return null;
        }
        return unlink(l);
    }

    public E pollLast() {
        return removeLast();
    }

  • 指定位置删除元素

    1
    2
    3
    4
    5
    6
    public E remove(int index) {
        if (index < 0 || index >= this.size) {
            return null;
        }
        return unlink(node(index));
    }

  • 清空链表

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    public void clear() {
        for (Node<E> x = this.first; x != null;) {
            Node<E> next = x.next;
            x.prev = null;
            x.item = null;
            x.next = null;
            x = next;
        }
        this.first = null;
        this.last = null;
        this.size = 0;
    }

  • 修改指定位置元素

    1
    2
    3
    4
    5
    6
    7
    8
    9
    public E set(int index, E element) {
        if (index < 0 || index >= this.size) {
            return null;
        }
        Node<E> x = node(index);
        E oldElement = x.item;
        x.item = element;
        return oldElement;
    }

扩展

将 “分块思想” 应用于链表之中，便得到了一种新的数据结构—— 块状链表。

相关文章