链式结构

LinkedList 的操作

作者 QIFAN 日期 2017-01-06
链式结构

重点在操作的实现。


关系图

Java 8 中,ListDequeQueueStackLinkedList 的关系如下图,箭头代表继承。
LinkedList 关系图

优缺点

  • 优点:长度可以动态改变,增删改的操作的复杂度为 $O(1)$
  • 缺点:
    • 查找需要遍历
    • 需要额外的 4 bytes 内存来存储下一个节点的指针

链表操作及实现

Java doc 选取其中几个来实现一下。其中会考虑到一些边际情况,就当锻炼思维了。

首先是节点 Node 的结构,包含一个变量 data 表示数据,另一个 Node 表示其下一个节点。

Extra Tip: 嵌套类
嵌套类分两种,static 和 non-static ,主要区别就是 non-static 类可以获取其他类中的成员变量,而 static 类则不可以。其实就是一种封装方式,如果一个嵌套类不需要去获取别的类的成员变量,则可将它声明为 static ,就像 LinkedList 中的 Node 。

static class Node<T> {
private T data;
private Node<T> next;
Node(T data, Node<T> next) {
this.data = data;
this.next = next;
}
}
  • 查找某个 key ,找到返回 true ,没找到就 false 。

    public boolean find(T key) {
    if (head == null) {
    return false;
    }
    Node<T> curr = head;
    while (curr != null) {
    if (curr.data.equals(key)) {
    return true;
    }
    curr = curr.next;
    }
    return false;
    }
  • 开头增加。相当于新建一个Node使其的 next 指向原来的 head

    public void addFirst(T toBeInserted) {
    head = new Node<T>(toBeInserted, head);
    }
  • 末尾增加,先遍历到尾巴。

    public void addLast(T toBeInserted) {
    if (head == null) {
    addFirst(toBeInserted);
    } else {
    Node<T> curr = head;
    while (curr.next != null) {
    curr = curr.next;
    }
    curr.next = new Node<T>(toBeInserted, null);
    }
    }
  • 在某个 key 前增加。先找 key ,并且存当前位置的前一个 Node 。

    public void addBefore(T toBeInserted, T key) {
    if (head == null) {
    return;
    }
    if (head.data.equals(key)) {
    addFirst(toBeInserted);
    } else {
    Node<T> curr = head;
    Node<T> pre = null;
    while (curr != null && !curr.data.equals(key)) {
    pre = curr;
    curr = curr.next;
    }
    if (curr != null) {
    pre.next = new Node<T>(toBeInserted, curr);
    }
    }
    }
  • 在某个 key 后增加。先找 key ,找到直接加上就行。

    public void addAfter(T toBeInserted, T key) {
    if (head == null) {
    return;
    }
    Node<T> curr = head;
    while (curr != null && !curr.data.equals(key)) {
    curr = curr.next;
    }
    if (curr != null) {
    curr.next = new Node<T>(toBeInserted, curr.next);
    }
    }
  • 删除开头,即替换 head 为 head.next 。

    public void deleteFirst() {
    if (head != null) {
    head = head.next;
    }
    }
  • 删除末尾。查看下一个节点是不是末尾(curr.next == null)。

    public void deleteLast() {
    if (head == null) {
    return;
    }
    if (head.next == null) {
    head = null;
    } else {
    Node<T> curr = head;
    while (curr.next.next != null) {
    curr = curr.next;
    }
    curr.next = null;
    }
    }
  • 删除指定节点。

    public void delete(T toBeDeleted) {
    if (head == null) {
    return;
    }
    if (head.data.equals(toBeDeleted)) {
    head = null;
    } else {
    Node<T> curr = head;
    while (curr.next != null && !curr.next.data.equals(toBeDeleted)) {
    curr = curr.next;
    }
    if (curr.next != null) {
    curr.next = curr.next.next;
    }
    }
    }
  • 删除指定节点的前一个。

    public void deleteBefore(T key) {
    if (head == null || head.next == null || head.data.equals(key)) {
    return;
    }
    if (head.next.data.equals(key)) {
    deleteFirst();
    } else {
    Node<T> curr = head;
    while (curr.next.next != null && !curr.next.next.data.equals(key)) {
    curr = curr.next;
    }
    if (curr.next.next != null) {
    curr.next = curr.next.next;
    }
    }
    }
  • 删除指定节点的后一个。

    public void deleteAfter(T key) {
    if (head == null) {
    return;
    }
    Node<T> curr = head;
    while(curr != null && !curr.data.equals(key)) {
    curr = curr.next;
    }
    if (curr != null && curr.next != null) {
    curr.next = curr.next.next;
    }
    }

完整代码: LinkedList.java



相关文章算法基础梳理



更新历史
+ 2017.01.06 第一版