链表

文章结构

  1. 链表的定义
  2. 链表的插入和删除操作
  3. 链表的特性
  4. 常见的链表结构
  5. 自定义链表
  6. 链表的经典操作
  7. 使用链表实现LRU算法

1. 链表的定义

链表也是一种线性表数据结构，链表不需要连续的存储空间，它通过“指针”将一组零散的内存块串联起来使用。链表和数组的内存结构对比如下图

链表与数组内存分布对比图

2. 链表的插入和删除操作

链表的插入和删除操作示意如下图


插入和删除节点示意图
  1. 插入操作代码实现
/**
     * 将元素node插入到prev的后面
     *
     * @param preNode
     * @param node
     */
    private void insert(Node<Integer> preNode, Node<Integer> node) {
        if (preNode == null) {
            return;
        } else {
            Node temp = preNode.next;
            preNode.next = node;
            node.next = temp;
        }
    }
  1. 删除操作代码实现
 /**
     * 删除preNode的后面一个节点
     *
     * @param preNode
     */
    private void delete(Node<Integer> preNode) {
        if (preNode.next != null) {
            preNode.next = preNode.next.next;
        }
    }

上面使用到的单链表节点定义

  private static class Node<T> {
        T item;
        Node<T> next;
  }

3. 链表的特性

  1. 链表插入和删除比较高效，时间复杂度为O(1)。因为链表的内存不连续，前后元素通过指针来确定，删除和插入时，不需要做数据搬移。
  2. 链表的随机访问比较低效，时间复杂度为O(n)。因为链表的内存不连续，需要从头遍历才能找到要查找的序号对应的元素

4. 常见的链表结构

  1. 单链表
  2. 循环链表
  3. 双向链表
单链表示意图

循环链表示意图
双向链表示意图

5. 自定义LinkedList

自定义LinkedList，支持添加、插入、替换、删除等基本操作。主要代码如下

public class MyLinkedList<E> {

    private int size;
    private Node<E> first;
    private Node<E> last;

    public MyLinkedList() {
    }

    /**
     * 添加
     *
     * @param e
     * @return
     */
    public boolean add(E e) {
        addToLast(e);
        return true;
    }

    /**
     * 插入
     *
     * @param index
     * @param e
     * @return
     */
    public boolean add(int index, E e) {
        checkPositionIndex(index);
        if (index == size) {
            addToLast(e);
        } else {
            addBefore(e, getNode(index));
        }
        return true;
    }

    /**
     * 替换
     *
     * @param index
     * @param e
     * @return
     */
    public E set(int index, E e) {
        checkElementIndex(index);
        Node<E> node = getNode(index);
        E oldItem = node.item;
        node.item = e;
        return oldItem;
    }

    /**
     * 删除指定索引位置的元素
     *
     * @param index
     * @return
     */
    public E remove(int index) {
        checkElementIndex(index);
        return remove(getNode(index));
    }

    /**
     * 删除特定元素
     *
     * @param node
     * @return
     */
    private E remove(Node<E> node) {
        E oldItem = node.item;
        if (node == first || node == last) {//删除头和尾需要特殊处理
            if (node == first) {
                if (node.next != null) {//node.next==null为只剩一个元素的情况
                    node.next.prev = null;
                }
                first = node.next;
            }
            if (node == last) {
                if (node.prev != null) {//node.prev==null为只剩一个元素的情况
                    node.prev.next = null;
                }
                last = node.prev;
            }
        } else {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
        node.item = null;
        size--;
        return oldItem;
    }

    /**
     * 获取指定索引位置的元素值
     *
     * @param index
     * @return
     */
    public E get(int index) {
        checkElementIndex(index);
        Node<E> node = getNode(index);
        return node.item;
    }

    public boolean remove(E e) {
        if (first != null) {
            Node<E> temp = first;
            if (e == null) {
                while (temp != null) {
                    if (temp.item == null) {
                        remove(temp);
                        return true;
                    } else {
                        temp = temp.next;
                    }
                }
            } else {
                while (temp != null) {
                    if (e.equals(temp.item)) {
                        remove(temp);
                        return true;
                    } else {
                        temp = temp.next;
                    }
                }
            }
        }
        return false;
    }


    private void addBefore(E e, Node<E> node) {
        Node<E> tempNode = new Node<>(e, node, node.prev);
        if (node == first) {
            node.prev = tempNode;
            first = tempNode;
        } else {
            node.prev.next = tempNode;
            node.prev = tempNode;
        }
        size++;
    }

    private void addToLast(E e) {
        if (first == null) {//空链表
            Node<E> node = new Node<>(e, null, null);
            first = node;
            last = node;
        } else {//非空链表
            Node<E> node = new Node<>(e, null, last);
            last.next = node;
            last = node;
        }
        size++;
    }


    public int size() {
        return size;
    }

    private Node<E> getNode(int index) {
        if (index < (size >> 1)) {//index在链表的左半边
            Node<E> e = first;
            for (int i = 0; i < index; i++) {
                e = e.next;
            }
            return e;
        } else {//index在链表的右半边
            Node<E> e = last;
            for (int i = size - 1; i > index; i--) {
                e = e.prev;
            }
            return e;
        }
    }

    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }

    private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

    private String outOfBoundsMsg(int index) {
        return "Index: " + index + ", Size: " + size;
    }


    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        public Node(E item, Node<E> next, Node<E> prev) {
            this.item = item;
            this.next = next;
            this.prev = prev;
        }
    }
}

完整代码和测试用例，请查看github之MyLinkedList源码

6. 常见的链表操作

  1. 单链表反转
  2. 链表中环的检测
  3. 合并两个有序的链表
  4. 删除链表倒数第n个节点
  5. 求链表的中间节点

6.1 单链表反转

实现思路：

新建一个空链表newHead；然后遍历原来的链表，依次取出节点插入到newHead的头部

代码实现

public static Node reverse(Node head) {
    Node current = head;
    Node newHead = null;
    while (current != null) {
        Node next = current.next;//保存当前节点的下一个节点
        current.next = newHead;//将当前遍历的节点插入到新链表的头部
        newHead = current;//移动新链表的头指针指向当前节点
        current = next;//将当前节点移动到下一个要遍历的节点
    }
    return newHead;
}

6.2 链表中环的检测

实现思路

使用两个指针去遍历链表，一个一次走两步，一个一次走一步，两个指针同时从前向后遍历链表，如果他们后面还能相遇，则说明有环

代码实现

public static boolean checkCircle(Node head) {
    if (head == null) {
        return false;
    }

    Node quick = head.next;
    Node slow = head;
    while (quick != null && quick.next != null) {
        quick = quick.next.next;
        slow = slow.next;
        if (slow == quick) {
            return true;
        }
        System.out.println("slow:" + slow.item);
    }
    return false;
}

6.3 合并两个有序的链表

实现思路

创建一个新的链表来存放合并后的结果，使用两个指针分别指向两个链表的头部，比较两个指针的值，将小的节点添加到新的列表中，并移动其指针到下一个节点，然后再次比较两个指针的值，重复这个过程直到一个链表遍历完毕。然后继续遍历未遍历完毕的链表剩下的节点插入到新的链表的后面

代码实现

public static Node mergeSortedList(Node head1, Node head2) {
        Node head = null;
        Node current = null;
        while (head1 != null && head2 != null) {
            Node temp = null;
            if (head1.item < head2.item) {
                temp = head1;
                head1 = head1.next;
            } else {
                temp = head2;
                head2 = head2.next;
            }
            if (head == null) {
                head = temp;
                current = head;
            } else {
                current.next = temp;
                current = temp;
            }
        }
        while (head1 != null) {
            if (head == null) {
                head = head1;
                current = head;
            } else {
                current.next = head1;
                current = head1;
            }
            head1 = head1.next;
        }
        while (head2 != null) {
            if (head == null) {
                head = head2;
                current = head;
            } else {
                current.next = head2;
                current = head2;
            }
            head2 = head2.next;
        }
        return head;
    }

6.4 删除链表倒数第n个节点

实现思路

先用一个指针从链表头部开始遍历k-1个节点，然后再用一个指针指向链表头部，两个指针同时开始向后遍历，当第一个指针遍历到链表的尾部时， 第二个指针指向的就是倒数第k个节点

代码实现

public static Node deleteLastKth(Node head, int k) {
    Node fast = head;
    int i = 1;
    while (fast != null && i < k) {
        fast = fast.next;
        i++;
    }
    if (fast == null) {//链表的元素不够k个
        return head;
    }
    Node slow = head;
    Node pre = null;
    while (fast.next != null) {
        fast = fast.next;
        pre = slow;
        slow = slow.next;
    }
    if (pre == null) {
        head = head.next;
    } else {
        pre.next = pre.next.next;
    }
    return head;
}

6.5 求链表的中间节点

实现思路

使用两个指针，一个指针一次走两步，一个指针一次走一步，两个指针同时从链表的头部向尾部遍历，当一次走两步的指针走到链表尾部时，一次走一步的指针指向的就是链表的中间元素

代码实现

public static Node findMiddleNode(Node head) {
    if (head == null) {
        return null;
    }
    Node fast = head.next;
    Node slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}

完整代码和测试用例，请查看github之LinkedListAlgo和LinkedListAlgoTest

7. 使用链表实现LRU算法

什么是LRU算法

LRU算法常用的一种缓存算法，它按照使用的时间排序，新进入的数据排在最前面，如果已经在缓存中的数据又被重新使用了，则重新把它排到最前面。当缓存满了的时候，从排在最后面的数据开始删除

简单的实现

实现一个简单限制最大缓存个数的LRU算法

代码实现

public class LRUBaseLinkedList<E> {
   
    private static final int DEFAULT_CAPACITY = 10;
    private int capacity;
    private int size;
    private Node<E> head;
    private Node<E> tail;

    public LRUBaseLinkedList() {
        this.capacity = DEFAULT_CAPACITY;
    }

    public void add(E e) {
        Node<E> node = findNode(e);
        if (node != null) {
            deleteElement(node);
            insertElementAtBegin(e);
        } else {
            if (size >= capacity) {
                deleteElementAtEnd();
            }
            insertElementAtBegin(e);
        }
    }

    public void printAll() {
        StringBuilder builder = new StringBuilder();
        Node<E> node = head;
        while (node != null) {
            builder.append(node.item + ",");
            node = node.next;
        }
        System.out.println("printAll:" + builder.toString());
    }

    private void deleteElementAtEnd() {
        if (tail != null) {
            deleteElement(tail);
        }
    }

    private void insertElementAtBegin(E e) {
        if (head == null) {
            Node<E> node = new Node<>(e, null, null);
            head = node;
            tail = node;
        } else {
            Node<E> node = new Node<>(e, head, null);
            head.prev = node;
            head = node;
        }
        size++;
    }

    private void deleteElement(Node<E> node) {
        if (node == head || node == tail) {
            if (node == head) {
                head = node.next;
                if (head != null) {//head!=tail
                    head.prev = null;
                }
            }
            if (node == tail) {
                tail = node.prev;
                if (tail != null) {//head!=tail
                    tail.next = null;
                }
            }
        } else {
            node.next.prev = node.prev;
            node.prev.next = node.next;
        }
        node.item = null;
        size--;
    }

    private Node<E> findNode(E e) {
        Node temp = head;
        while (temp != null) {
            if (temp.item.equals(e)) {
                return temp;
            } else {
                temp = temp.next;
            }
        }
        return null;
    }

    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        public Node() {
        }

        public Node(E item, Node<E> next, Node<E> prev) {
            this.item = item;
            this.next = next;
            this.prev = prev;
        }
    }
}

完整代码和测试用例，请查看github之LRUBaseLinkedList和LRUBaseLinkedListTest

说明

文中图片来源：极客时间，王争《数据结构与算法之美》

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 213,014评论 6赞 492
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 90,796评论 3赞 386
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 158,484评论 0赞 348
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 56,830评论 1赞 285
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 65,946评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,114评论 1赞 292
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,182评论 3赞 412
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,927评论 0赞 268
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,369评论 1赞 303
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,678评论 2赞 327
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,832评论 1赞 341
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,533评论 4赞 335
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,166评论 3赞 317
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,885评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,128评论 1赞 267
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,659评论 2赞 362
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,738评论 2赞 351