文档章节

链表

O
 Oaki
发布于 02/14 22:40
字数 1194
阅读 127
收藏 0

知识点

链表是动态数据结构。

链表的数据存储在”节点“(Node)中。

class Node {
    E e;
    Node next;
}

当 next 为 NULL,说明当前节点为最后一个节点。

优点:真正的动态,不需要处理固定容量的问题。

缺点:丧失了随机访问的能力。

数组和链表的对比:

  • 数组最好用于索引有语义的情况,最大的优点是快速查询。
  • 链表不适合用于索引有语义的情况,最大的优点是动态。

重要性:

  • 最简单的动态数据结构
  • 更深入地理解引用(或者指针)
  • 更深入的理解递归
  • 辅助组成其他数据结构

复杂度分析:

  • 增:O(n)
  • 删:O(n)
  • 改:O(n)
  • 查:O(n)

代码(有虚拟头)

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

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

    }

    private Node dummyHead;
    private int size;

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

    /**
     * 获取链表中的元素个数
     *
     * @return
     */
    public int getSize() {
        return size;
    }

    /**
     * 返回链表是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 在链表的 index(0-based) 位置添加新的元素 e
     *
     * 在链表中不是一个常用的操作,练习用:)
     *
     * 关键:找到要添加的节点的前一个节点
     *
     * 时间复杂度:O(n/2) = O(n)
     *
     * @param index
     * @param e
     */
    public void add(int index, E e) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Add failed. Illegal index.");
        }

        // 找到要添加的节点的前一个节点
        Node prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }

        // 第一种写法
        // Node node = new Node(e);
        // node.next = prev.next;
        // prev.next = node;

        // 第二种写法
        prev.next = new Node(e, prev.next);
        size++;
    }

    /**
     * 在链表头添加新的元素 e
     *
     * 时间复杂度:O(1)
     *
     * @param e
     */
    public void addFirst(E e) {
        add(0, e);
    }

    /**
     * 在链表末尾添加新的元素 e
     *
     * 时间复杂度:O(n)
     *
     * @param e
     */
    public void addLast(E e) {
        add(size, e);
    }

    /**
     * 获得链表的第 index(0-based) 个位置的元素
     *
     * 在链表中不是一个常用的操作,练习用:)
     *
     * @param index
     */
    public E get(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Get failed. Illegal index.");
        }

        Node cur = dummyHead.next;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }

        return cur.e;
    }

    /**
     * 获得链表的第一个元素
     *
     * @return
     */
    public E getFirst() {
        return get(0);
    }

    /**
     * 获得链表的最后一个元素
     *
     * @return
     */
    public E getLast() {
        return get(size - 1);
    }

    /**
     * 修改链表的第 index(0-based) 个位置的元素为 e
     *
     * 在链表中不是一个常用的操作,练习用:)
     *
     * 时间复杂度:O(n)
     *
     * @param index
     * @param e
     */
    public void set(int index, E e) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Set failed. Illegal index.");
        }

        Node cur = dummyHead.next;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }

        cur.e = e;
    }

    /**
     * 查找链表中是否有元素 e
     *
     * 时间复杂度:O(n)
     *
     * @param e
     * @return
     */
    public boolean contains(E e) {
        Node cur = dummyHead.next;
        while (cur != null) {
            if (cur.e.equals(e)) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    /**
     * 从链表中删除 index(0-based) 位置的元素,返回删除的元素
     *
     * 在链表中不是一个常用的操作,练习用:)
     *
     * 时间复杂度:O(n/2) = O(n)
     *
     * @param index
     * @return
     */
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Remove failed. Illegal index.");
        }

        Node prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }

        Node retNode = prev.next;
        prev.next = retNode.next;
        retNode.next = null;
        size--;

        return retNode.e;
    }

    /**
     * 从链表中删除第一个元素,返回删除的元素
     *
     * 时间复杂度:O(1)
     *
     * @return
     */
    public E removeFirst() {
        return remove(0);
    }

    /**
     * 从链表中删除最后一个元素,返回删除的元素
     *
     * 时间复杂度:O(n)
     *
     * @return
     */
    public E removeLast() {
        return remove(size - 1);
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();

        Node cur = dummyHead.next;
        while (cur != null) {
            res.append(cur + "->");
            cur = cur.next;
        }
        // for (Node cur = dummyHead.next; cur != null; cur = cur.next) {
        //     res.append(cur + "->");
        // }
        res.append("NULL");


        return res.toString();
    }
}

代码(没有虚拟头,有尾指针,待补全)

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

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

    }

    private Node head;
    private Node tail;
    private int size;

    public LinkedListWithTail() {
        head = null;
        tail = null;
        size = 0;
    }

    /**
     * 获取链表中的元素个数
     *
     * @return
     */
    public int getSize() {
        return size;
    }

    /**
     * 返回链表是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 在链表末尾添加新的元素 e
     *
     * @param e
     */
    public void addLast(E e) {
        if (tail == null) {
            tail = new Node(e);
            head = tail;
        } else {
            tail.next = new Node(e);
            tail = tail.next;
        }
        size++;
    }

    /**
     * 从链表中删除第一个元素,返回删除的元素
     *
     * @return
     */
    public E removeFirst() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Remove failed. LinkedList is empty.");
        }

        Node retNode = head;
        head = head.next;
        retNode.next = null;
        if (head == null) {
            tail = null;
        }
        size--;

        return retNode.e;
    }

    /**
     * 获得链表的第一个元素
     *
     * @return
     */
    public E getFirst() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Get failed. LinkedList is empty.");
        }
        return head.e;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();

        Node cur = head;
        while (cur != null) {
            res.append(cur + "->");
            cur = cur.next;
        }
        res.append("NULL");


        return res.toString();
    }
}

© 著作权归作者所有

O
粉丝 0
博文 13
码字总数 8236
作品 0
私信 提问
加载中

评论(0)

[算法总结] 一文搞懂面试链表题

本文首发于我的个人博客:尾尾部落 链表是面试过程中经常被问到的,这里把剑指offer 和 LeetCode 中的相关题目做一个汇总,方便复习。 1. 在 O(1) 时间删除链表节点 题目描述:给定单向链表的...

繁著
2018/08/28
0
0
学习笔记-Redis设计与实现-链表

链表提供了高效的节点重排能力,以及顺序性的节点访问方式,并且可以通过删除节点来灵活地调整链表地长度。 当一个列表键包含了数量比较多地元素,又或者列表中包含的元素都是比较长的字符串...

技术小阿哥
2017/11/27
0
0
单双链表练习题

本文是关于链表的一些操作(包括单链表和双向循环链表) 1、单链表,双链表的创建。 2、单链表和双链表的打印。 3、单链表的插入,删除。 4、双链表的插入和删除。 5、单链表的逆置。 6、单链...

qq_38646470
2018/01/27
0
0
数据结构——基于java的链表实现(真正理解链表这种数据结构)

原创不易,如需转载,请注明出处https://www.cnblogs.com/baixianlong/p/10759599.html,否则将追究法律责任!!! 一、链表介绍 1、什么是链表? 链表是一种物理存储结构上非连续、非顺序的...

会炼钢的小白龙
2019/04/23
0
0
刷题|和链表相关的题目思路分析与总结

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 https://blog.csdn.net/darlingwood2013/article/details/98310291 刷题|和链表相关的题目思...

叶晚林
2019/08/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

金三银四——离大厂offer你就只差一张路线图

很多人做Java开发4,5年后,都会感觉自己遇到瓶颈。什么都会又什么都不会,如何改变困境,为什么很多人写了7,8年还是一个码农,工作中太多被动是因为不懂底层原理。公司的工作节奏又比较快,...

Java天天
29分钟前
32
0
用Java递归删除目录

有没有办法用Java递归删除整个目录? 在正常情况下,可以删除一个空目录。 但是,要删除带有目录的整个目录,就不再那么简单了。 如何用Java删除包含目录的整个目录? #1楼 具有堆栈且没有递...

javail
30分钟前
95
0
在hbuilderx中vue-cli脚手架配置router文件夹

配置router文件 新建一个文件夹router,再在新建的router文件夹里新建一个index.js文件 index.js import Vue from 'vue' import Router from 'vue-router' import Home from '../components......

软件开发小白
38分钟前
57
0
高并发软件层面解决思路-从前端到后端

1、页面缓存、前后端分离、CDN、静态页面(减少后台接口请求,需要CMS系统支持)、代码等优化(百度关键词“雅虎前端优化”) 2、nginx或其它配置合理的负载均衡策略,按主机性能设置合理的权...

无名氏的程序员
53分钟前
69
0
Maven项目使用打包时使用本地jar包库

在使用maven管理项目时,有时候我们可能会使用一些第三方的jar包依赖库,但是这些jar包依赖库又没有在共有的maven仓库。 通常只能下来放到本项目的lib目录下。但是我们打包时如果不做处理,那...

上官胡闹
今天
39
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部