转载

纯数据结构Java实现(3/11)(链表)

题外话: 篇幅停了一下，特意去看看其他人写的类似的内容；然后发现类似博主喜欢画图，喜欢讲解原理。

(于是我就在想了，理解数据结构的确需要画图，但我的文章写给懂得人看，只配少量图即可，省事儿)

下面正题开始。

一般性的，都能想到 dummy head 的技巧以及Java中LinkedList(底层是双向(循环)链表)。

Leetcode 返回一个头结点对象，就算返回整个链表了，而我们自己实现一般会 new 一个链表对象实例，然后调用该实例的各类方法来操作整个链表。

单链表

基本认识

之前写的动态数组并非真正动态，因为其内部封装的是一个容量不可变的静态数组。

而这里的链表则是真正的 动态数据结构 (不需要处理固定容量问题，即增删效率高，但由于不知道实际地址/索引，所以也丧失了随机访能力)。

辅助其他数据结构：二分搜索树，AVL/红黑树，它们基于链表实现。

基本构成: 节点 + 指针。

class Node {
    E e;
    Node next;
}
  • 最后一个节点一般指向 null

为了方便或者统一操作，一般会有 Node head，头结点。

  • 头结点的存在一般是为了在头部操作 (就像动态数组的新元素索引始终是 size 位置)
  • 一般直接用头结点指向首个节点(第一个节点即 head，但它不存储元素) dummy head

之所以用 dummy head 的原因，其实是为了操作简便。(不用也可以，但实现上的写法就...)

  • 打个比方，你要删除/增加某个节点时，一般情况而言，一定要知道删除节点的前一个节点(在头部则没有必要)；一般都是通过循环遍历往后先找到特定节点，但是如果没有 dummy head，那么就要区分是在头结点还是中间节点操作(在脑海中想一下就知道了)。

有了 dummy head，头结点前面也有节点了，所以整个操作行为是统一的，一致的，不需要再做情况区分。

(下面有案例)

实现框架

先把实现的框架列一下，大致如下:

package linkedlist;

public class LinkedList<E> {

    //定义一个内部类，作为节点类
    private class Node {
        public E e;
        public Node next; //便于 LinkedList 访问

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

        public Node(E e){
            this(e, null);
        }

        public Node(){
            this(null, null);
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    //操作链表的辅助变量
    private int size;
    private Node head; //头结点

    //构造函数
    public LinkedList() {
        head = null;
        size = 0;
    }


    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }


}

然后再来实现其中的增删改查，此时先不设置虚拟头节点。

添加操作

这里实现的头部添加 (后续再扩展其他添加):

public void addFirst(E e) {
        /*
        Node node = new Node(e);
        node.next = head;
        head = node;
        */

        //简写
        head = new Node(e, head);

        //维护链表长度
        size++;
    }

在 某个位置 插入元素:

  • 情况1: 链表中间的节点，先找到相应位置 前一个节点 ，然后创建新节点，插入

纯数据结构Java实现(3/11)(链表)

纯数据结构Java实现(3/11)(链表)

  • 情况2: 如果是第一个节点，那么是不存在前一个节点的。直接用 addFirst 的方式
//指定的 index 位置添加元素 (先要找到 index 前一个位置)
    // index 从 0 ~ size-1
    public void add(int index, E e) {
        // 索引有问题
        if (index < 0 || index > size) { //当 index == size 时，表示在末尾添加
            throw new IllegalArgumentException("Add Failed, Illegal index");
        }
        if (index == 0) {
            addFirst(e);
        } else {
            Node prev = head;
            //找到指定位置前一个节点
            for (int i = 0; i < index - 1; i++) {
                prev = prev.next;
            }
            //创建一个新节点
            /*Node node = new Node(e);
            node.next = prev.next;
            prev.next = node;*/

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

(可以看到上面确实是区分不同的情况了的)

此时在末尾添加元素，即 index = size 的位置添加，直接调用 addLast 即可:

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

头结点优化

不着急往后探索，这里先把头节点优化一下，即加入 dummy head，统一整个操作流程。

上面的操作 add ，由于链表头结点 head 并没有前面一个节点，所以插入的时候确实要特殊一些。(如果第一个节点之前有节点，那么整个操作就统一了)

优化方法，在头结点前面添加一个 虚拟节点 ，即不存储任意元素的节点。

纯数据结构Java实现(3/11)(链表)

内部机制，用户(client) 不知道虚拟节点的存在。(只是为了方便逻辑操作)。

相关修改:

构造函数需要修改，初始化 LinkedList 的时候就要创建一个节点

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

添加元素可以统一用 add，然后让 addFirst 和 addLast 调用 add 方法即可。

//指定的 index 位置添加元素 (先要找到 index 前一个位置)
    // index 从 0 ~ size-1
    public void add(int index, E e) {
        // 索引有问题
        if (index < 0 || index > size) { //当 index == size 时，表示在末尾添加
            throw new IllegalArgumentException("Add Failed, Illegal index");
        }

        //因为在实际 index 取值范围内，总能找到相关节点的前一个节点
        Node prev = dummyHead;
        //找 index 之前的节点
        for(int i = 0; i < index; i++){
            prev = prev.next;
        }
        prev = new Node(e, prev.next);
        size++;
    }

    //头部插入
    public void addFirst(E e) {
        add(0, e);
    }

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

虚拟头结点的引入，方便了其他许多链表的操作(只要涉及类似的遍历查找)。

获取操作

//获取某元素
    public E get(int index) {
        //先检查索引的合法性
        if(index<0 || index > size-1) {
            throw new IllegalArgumentException("Get Failed, Illegal index");
        }

        // 和前面找 index 节点前一个节点不同(那里是从第一个节点前面的虚拟节点开始)
        // 这里就要找 index 节点，索引从 dummyHead.next 开始，即真正的第一个节点开始
        Node ret = dummyHead.next;
        for(int i =0; i < index; i++) {
            ret = ret.next;
        }
        return ret.e;
    }

获取第一个元素，最后一个:

//获取第一个
    public E getFirst() {
        return get(0);
    }
    
    //获取最后一个
    public E getLast() {
        return get(size -1);
    }

修改元素

把 index 位置的元素修改为 E。

(找到节点，然后替换里面的元素 e)

public void set(int index, E e) {
        //先检查索引的合法性
        if (index < 0 || index > size - 1) {
            throw new IllegalArgumentException("Get Failed, Illegal index");
        }
        //找到节点，然后替换里面的元素
        Node curr = dummyHead.next;
        for (int i = 0; i < index; i++) {
            curr = curr.next;
        }
        curr.e = e;
    }

查找元素

一直遍历到元素末尾，然后寻找尾巴。

//查找元素
    public boolean contains(E e) {
        Boolean ret = false;
        //在 size 范围内遍历查找
        Node curr = dummyHead.next;
        /*for(int i=0; i<size; i++){
            if(curr.e.equals(e)){
                ret = true;
                break;
            }
            curr = curr.next;
        }*/

        //其实可以用 while 循环 (多判断一次 size 位置)
        while(curr != null) {
            //当前节点是有效节点
            if(curr.e.equals(e)){
                ret = true;
                break;
            }
            curr = curr.next;
        }
        return ret;
    }

遍历打印

多种循环的写法:

//打印方法
    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();

        //从头遍历到尾巴
        /*Node curr = dummyHead.next;
        while(curr != null) {
            res.append(curr + "->");
            curr = curr.next;
        }*/
        //简写
        for(Node curr = dummyHead.next; curr != null; curr = curr.next) {
            res.append(curr + "->");
        }
        res.append("null");
        return res.toString();
    }

简单测试一下:

//测试元素
    public static void main(String[] args) {
        LinkedList1<Integer> linkedlist = new LinkedList1<>();
        //放入元素 0, 1, 2, 3, 4
        for(int i =0; i < 5; i++) {
            linkedlist.addFirst(i); //O(1)
            System.out.println(linkedlist);
        }

        System.out.println(linkedlist);

        //尝试插入一个元素
        linkedlist.add(1, 100); // 4, 100, 2, 3, 1, 0, null
        System.out.println(linkedlist);

    }

打印结果:

0->null
1->0->null
2->1->0->null
3->2->1->0->null
4->3->2->1->0->null
4->3->2->1->0->null
4->100->3->2->1->0->null

删除元素

还是要 先找到前一个节点 。(也就是说还是借助虚拟头结点)

纯数据结构Java实现(3/11)(链表)

简单一句话，然 delNode 和原来的链表脱离。(delNode 置空非必须)

编码实现:

//删除元素
    public E remove(int index){
        if (index < 0 || index > size - 1) {
            throw new IllegalArgumentException("Delete Failed, Illegal index");
        }

        //找到相关节点的前一个节点
        Node curr = dummyHead;
        for(int i = 0; i < index; i++) {
            curr = curr.next;
        }
        Node delNode = curr.next;
        //删除
        curr.next = delNode.next;
        delNode.next = null;

        //必须维护 size
        size--;

        return delNode.e;
    }

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

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

    //删除指定元素
    public void removeElem(E e) {
        //从 dummyHead 开始找，找到就删除，否则就不删除
        Node curr = dummyHead;
        boolean found = false;
        while (curr.next != null) {
            if (curr.next.e.equals(e)) {
                found = true;
                //删除操作
                Node delNode = curr.next;
                curr.next = delNode.next;
                delNode.next = null;
                size--;
                break;
            }
            curr = curr.next;
        }

        if (!found) {
            throw new RuntimeException("要删除的元素不存在");
        }
    }

测试一下:

//测试元素
    public static void main(String[] args) {
        LinkedList1<Integer> linkedlist = new LinkedList1<>();
        //放入元素 0, 1, 2, 3, 4
        for(int i =0; i < 5; i++) {
            linkedlist.addFirst(i); //O(1)
            System.out.println(linkedlist);
        }

        System.out.println(linkedlist);

        //尝试插入一个元素
        linkedlist.add(1, 100); // 4, 100, 2, 3, 1, 0, null
        System.out.println(linkedlist);


        //尝试删除 index = 1 位置的 100
        linkedlist.remove(1);
        System.out.println(linkedlist); //4->3->2->1->0->null

        //删除最后一个元素 0
        linkedlist.removeLast();
        System.out.println(linkedlist); //4->3->2->1->null
      
        //删除第一个元素
        linkedlist.removeFirst();
        System.out.println(linkedlist); //3->2->1->null     
      
        //删除指定元素
        linkedlist.removeElem(3);
        linkedlist.removeElem(1);
        //linkedlist.removeElem(null);
        System.out.println(linkedlist);
    }

时间复杂度

链表虽然不移动元素，但是涉及到从前往后找到(检查)相应的位置/元素。

添加操作:

  • addFirst(), O(1) 因为采用的是头插法
  • addLast(), O(n) 涉及循环遍历到尾部，然后插入
  • add(), O(n) 其实是 O(n/2) 即 O(n)

删除操作:

同上。

修改操作: O(n)。

查找操作:

get(), contains(), find() 一律 O(n)，因为并不支持随机访问呀。

单链表应用

链栈

上面也说了， 如果只在链表头增删时，它的整体复杂度是 O(1) ，这不正好用于栈么？

  • 简单记忆一下，同侧操作
  • 栈的底层实现是链表，而不是动态数组了
package stack;

import linkedlist.LinkedList1;  //这是有 dummy head优化的链表实现

public class LinkedListStack<E> implements Stack<E>{

    //链栈内部实际采用链表存储
    private LinkedList1<E> list;


    public LinkedListStack(){
        list = new LinkedList1<>();
    }

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

    @Override
    public int getSize() {
        return list.getSize();
    }

    @Override
    public E pop() {
        return list.removeFirst();
    }

    @Override
    public E peek() {
        return list.getFirst();
    }

    @Override
    public void push(E e) {
        list.addFirst(e);
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("Stack: top [");
        res.append(list);
        res.append("]");
        return res.toString();
    }

    public static void main(String[] args) {
        LinkedListStack<Integer> stack = new LinkedListStack<>();
        //放入元素 0, 1, 2, 3, 4
        for(int i =0; i < 5; i++) {
            stack.push(i); //O(1)
            System.out.println(stack);
        }

        System.out.println(stack);
        System.out.println(stack.peek());

        //弹出一个元素
        stack.pop();
        System.out.println(stack);
    }
}

测试结果:

Stack: top [0->null]
Stack: top [1->0->null]
Stack: top [2->1->0->null]
Stack: top [3->2->1->0->null]
Stack: top [4->3->2->1->0->null]
Stack: top [4->3->2->1->0->null]
4
Stack: top [3->2->1->0->null]

和数组实现的栈的不同，数组是在尾巴上插入，可能涉及动态扩容，均摊复杂度是 O(1)，而链栈始终就是O(1)。

  • 但是 linkedlist 的 new 操作时非常耗时的 ( 特别是大量对象创建 )
  • 真实运行结果是不确定的 (ArrayStack VS LinkedListStack)，因为数量级一致

链队列

因为队列涉及头和尾的操作，所以如果用链表，那一般要添加一个尾指针。

因为 head 和 tail 都是指针，所以入队和出队相当于改变指向那么简单，但谁做头谁做尾巴？（相当于 head, tail 指针往哪个方向移动）

如果要删除 tail 元素并不容易(无法做到O(1))，因为删除元素要知道 tail 前面一个元素。但是 tail 增加，则可以直接添加。(head不用管， 它的增删都比较容易)

所以结论显而易见:

  • tail 用作队尾 (即用于增加元素, tail 指针右移)
  • head 用作队首 (删除元素，出队)

此时还需要 dummy head 么，分析上面的 tail， head，显然不需要操作统一了，所以不需要哑结点。

这里就不复用 LinkedList 了，而是专门再在内部实现链式存储。(Node 内部类还是需要的)

特别注意:

  • 链表为空的情况
  • 只有一个元素的情况，此时即便是出队，也要 head = tail = null;
//内部采用链式存储的队列
public class LinkedQueue<E> implements Queue<E> {

    //定义一个内部类，作为节点类
    private class Node {
        public E e;
        public Node next; //便于 LinkedList 访问

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

        public Node(E e) {
            this(e, null);
        }

        public Node() {
            this(null, null);
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    private Node head, tail;
    private int size;

    //构造器
    public LinkedQueue() {
        head = tail = null;
        size = 0;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public E dequeue() {
        //出队操作，在队首
        //没有元素肯定就不能出队
        if (isEmpty()) {
            //或者 head = null
            throw new IllegalArgumentException("Cannot dequeue from an empty queue");
        }
        //正常出队，提取 head
        Node retNode = head; //tail，考虑只有一个元素的队列
        head = retNode.next;
        retNode.next = null;//游离对象

        //仅在只有一个元素的队列，需要维护 tail
        if (head == null) {
            tail = null;
        }

        size--;
        return retNode.e;
    }

    @Override
    public E getFront() {
        if (isEmpty()) {
            //或者 head = null
            throw new IllegalArgumentException("Cannot dequeue from an empty queue");
        }
        return head.e; // 返回队首即可
    }

    @Override
    public void enqueue(E e) {
        //入队操作，在尾部操作
        if (tail == null) { //说明此时队列是空的，即 tail 和 head 都为空
            tail = new Node(e);
            head = tail;
        } else {
            tail.next = new Node(e);
            tail = tail.next;
        }
        size++;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("Queue: front[ ");
        for(Node curr = head; curr != null; curr = curr.next){
            res.append(curr.e + "->");
        }
        res.append("null ] tail");
        return res.toString();
    }

    public static void main(String[] args) {
        LinkedQueue<Integer> queue = new LinkedQueue<>();

        //存储  11 个元素看看
        for(int i=0; i<11; i++){
            queue.enqueue(i);
            System.out.println(queue); // 在 10 个元素满的时候回扩容
        }
        //出队试试
        System.out.println("------出队");
        queue.dequeue();
        System.out.println(queue);
    }
}

运行结果如下:

Queue: front[ 0->null ] tail
Queue: front[ 0->1->null ] tail
Queue: front[ 0->1->2->null ] tail
Queue: front[ 0->1->2->3->null ] tail
Queue: front[ 0->1->2->3->4->null ] tail
Queue: front[ 0->1->2->3->4->5->null ] tail
Queue: front[ 0->1->2->3->4->5->6->null ] tail
Queue: front[ 0->1->2->3->4->5->6->7->null ] tail
Queue: front[ 0->1->2->3->4->5->6->7->8->null ] tail
Queue: front[ 0->1->2->3->4->5->6->7->8->9->null ] tail
Queue: front[ 0->1->2->3->4->5->6->7->8->9->10->null ] tail
------出队
Queue: front[ 1->2->3->4->5->6->7->8->9->10->null ] tail

到这里，单链表基本探究完毕了。

其他链表

下面说的这些链表其实也很常用，但是个人要去实现的话，就费事儿啊

(除非你是大学教师，或者学生，或者自由作家，有的是时间耐得住寂寞，磨啊)

双向链表

这个维护代价其实有点大，有点就是节点之间的联系更加方便了。(单链表时也会维护尾指针)

  • 比如尾端删除，不用从头开始找尾端前一个元素了，避免了 O(n) 复杂度

纯数据结构Java实现(3/11)(链表)

没有对比就没有伤害，要找我前一个节点是吧，直接给你(不要循环了)。其他操作则没有太多变化( 需要头结点优化 )。由于有额外的变量需要维护，所以并不见得简单。 

class Node {
    E e;
    Node prev, next;
}

循环链表

jdk 中 linkedlist 貌似经过一阵子去环优化，可能，因为不要环效率也不差。

循环链表一般都是基于双向链表的。

不用画图了，直接认为尾部元素直接指向 dummy head 即可。

此时不需要 tail，因为在 dummyHead 的前面添加一个元素，就相当于在结尾添加元素了。

(引入的环会导致操作有些许变化，比如遍历)

数组链表

  • 数组中除了存储值，还存储了下一个节点的索引，那么就相当于数组链表了。
  • 不依赖数组本身的 index，而依赖于自身存储的数字索引。

纯数据结构Java实现(3/11)(链表)

有点儿类似于数据库存储设计中的无限级字段，即某个元素要存储其父元素位置(parentId)。

毕竟还是基础数据结构，没有太复杂；这种 link 的思想用于树(二叉树，多叉树)很平常。

老规矩，代码参考的话，我放在了 gayhub , FYI。

原文  http://www.cnblogs.com/bluechip/p/self-pureds-linkedlist.html
正文到此结束
所属分类： Java 编程技术

热门推荐

相关文章

阿里云首购8折
说给你听

本文目录
随机标签
书籍教程
springboot-demo Java入门教程 bootstrap3 CSS Apache基础教程 php ionic 教程 Python mysql教程 eclipse Ubuntu VPS系统配置 AngularJS 教程 MongoDB教程 Struts2教程 Redis教程 Spring教程 Git教程 Jenkins进阶系列 openfire参考指南 Java设计模式 HBase教程 Maven教程 hibernate教程 Docker 教程 memcached教程 Quartz指南 Hive教程 Ant教程 ANTLR教程 SpringCloud java实例教程 springcloud-demo XStream教程 Hazelcast教程 Elastic-Job-Lite 深入浅出MyBatis SVN教程 ibaties教程 rabittmq教程 solr教程 Hadoop教程 WebService CXF学习 JPA教程 ActiveMQ中文指南 java-demo Java内存模型 dubbo教程 python3-demo Linux入门视频教程
近期评论
  1. 1 Spring Cloud Consul实现选举机制
  2. 2 Spring Boot集成ShedLock实现分布式定时任务
  3. 3 利用oss进行数据库和网站图片备份
  4. 4 Spring Cloud Stream实现数据流处理
  5. 5 Python3访问MySQL数据库快速入门Demo
  6. 6 Github开源项目作者可以免费申请 JetBrains 全家桶
  7. 7 Spring Cloud Vault快速入门Demo
  8. 8 Spring Cloud Gateway快速入门Demo
  9. 9 Spring Cloud Contract快速入门Demo
  10. 10 Spring Cloud Consul快速入门Demo
网站信息
  • 文章总数：82,714 篇
  • 文件总数：284,287 个
  • 标签总数：2,393 个
  • 分类总数：85 个
  • 留言数量：2,560 条
  • 在线人数：649 人
  • 运行天数：4,408天
  • 最后更新：2024年11月21日23点
Loading...

其他链接

关于本站

本站定位：个人技术类博客

本站作用：写博客、记日志、闲聊扯淡鼓捣技术。

问题交流

[HBLOG]公众号 HBLOG HBLOG