目录介绍

  • 01.链表特点
    • 1.1 什么是链表
    • 1.2 链表优缺点
    • 1.3 为何用链表
  • 02.链表分类
    • 2.1 单向链表
    • 2.2 双向链表
    • 2.3 循环链表

好消息

  • 博客笔记大汇总【16年3月到至今】，包括Java基础及深入知识点，Android技术博客，Python学习笔记等等，还包括平时开发中遇到的bug汇总，当然也在工作之余收集了大量的面试题，长期更新维护并且修正，持续完善……开源的文件是markdown格式的！同时也开源了生活博客，从12年起，积累共计N篇[近100万字，陆续搬到网上]，转载请注明出处，谢谢！
  • 链接地址：https://github.com/yangchong211/YCBlogs
  • 如果觉得好，可以star一下，谢谢！当然也欢迎提出建议，万事起于忽微，量变引起质变！

01.链表特点

1.1 什么是链表

  • 链表是一种用于存储数据集合的数据结构。主要有哪些属性呢，如下所示：
    • 链表是由内存中一系列不相连的结构组成
    • 一种线性表，但是并不会按线性的顺序存储数据
    • 每一个结构均含有表元素和next指针，最后一个元素的后续指针是NULL
    • 程序执行过程中，链表长度可以增加和缩小
    • 没有内存空间的浪费，但是指针需要一些额外的内存开销
  • 链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理，如何理解这句话？

1.2 链表优缺点

  • 优点是插入和删除比较方便(不需移动其他元素, 只需改变指针)，缺点是访问效率低，存储空间利用率低。

1.3 为何用链表

  • 使用链表结构可以克服数组需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。

02.链表分类

2.1 单向链表

  • 单链表是链表中结构最简单的。
    • 一个单链表的节点(Node)分为两个部分，第一个部分(data)保存或者显示关于节点的信息，另一个部分存储下一个节点的地址。最后一个节点存储地址的部分指向空值。
  • 结构图如下所示
    • image
      image
  • 单链表的节点类
    //链表的每个节点类
private class Node{
    private Object data;//每个节点的数据
    private Node next;//每个节点指向下一个节点的连接
    
    public Node(Object data){
        this.data = data;
    }
}

2.2 双向链表

  • 为什么会有双向链表
    • 对于单项链表，我们如果想在尾部添加一个节点，那么必须从头部一直遍历到尾部，找到尾节点，然后在尾节点后面插入一个节点。这样操作很麻烦，如果我们在设计链表的时候多个对尾节点的引用，那么会简单很多。
  • 结构图如下图所示[LinkedList中双向链表]
    • LinkedList内部结构
      LinkedList内部结构
  • 双向链表的节点类：博客
    • 这个类就代表双端链表的节点Node。这个类有三个属性，分别是前驱节点，本节点的值，后继结点。
    private static class Node<E> {
    E item;//节点值
    Node<E> next;//后继节点
    Node<E> prev;//前驱节点

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

2.3 循环链表

  • 如下所示
    • image
      image
  • 循环链表的节点类

其他介绍

01.关于博客汇总链接

02.关于我的博客

  • github：https://github.com/yangchong211
  • 知乎：https://www.zhihu.com/people/yczbj/activities
  • 简书：http://www.jianshu.com/u/b7b2c6ed9284
  • csdn：http://my.csdn.net/m0_37700275
  • 喜马拉雅听书：http://www.ximalaya.com/zhubo/71989305/
  • 开源中国：https://my.oschina.net/zbj1618/blog
  • 泡在网上的日子：http://www.jcodecraeer.com/member/content_list.php?channelid=1
  • 邮箱：yangchong211@163.com
  • 阿里云博客：https://yq.aliyun.com/users/article?spm=5176.100- 239.headeruserinfo.3.dT4bcV
  • segmentfault头条：https://segmentfault.com/u/xiangjianyu/articles
  • 掘金：https://juejin.im/user/5939433efe88c2006afa0c6e
贡献者: yangchong211