数据结构——链表（一）

链表基础

链表

链表是由一组不必相连【不必相连：可以连续也可以不连续】的内存结构，按特定的顺序链接在一起的抽象数据类型。是一种线性表，但是并不会按线性的顺序存储数据，而是在由一个个节点组成，节点一般包含存放数据的数据域和存放指针的指针域。

补充：
    抽象数据类型（Abstract Data Type [ADT]）：表示数学中抽象出来的一些操作的集合。
    内存结构：内存中的结构，如：struct、特殊内存块...等等之类；

下图就是一种简单的链表


单-图1.png

对比数组

数组是在相连的内存空间，由相同数据类型的元素组成的集合。

数组.jpg

相同点

  1. 都是用来存储和操作数据的

  2. 都是数据结构中的线性结构

不同点

  1. 数组是顺序的存储结构，也就是连续的内存空间；链表是链式的存储结构，内存空间离散排列的（当然也可以是连续的）

  2. 链表通过指针来连接元素与元素，数组则是把所有元素按次序依次存储。

  3. 链表的插入删除元素相对数组较为简单，不需要移动元素，且较为容易实现长度扩充，但是寻找某个元素较为困难

  4. 数组寻找某个元素较为简单，但插入与删除比较复杂，由于最大长度需要再申请内存空间时指定，所以扩容不如链表方便

分类

一般来说，链表常用的有 3 类： 单向链表、双向链表、循环链表（单链循环，双链循环）。

单向链表

单向链表的节点由一个具体的数据域和指向下一个节点的指针域组成。所以单链表只能单向读取、查找和遍历。

单-图1.png

双向链表

双向链表的节点由一个具体的数据域和指向上一个节点以及指向下一个节点的指针域组成。所以双向链表可以双向读取、查找和遍历。

双-图1.png

循环链表

单向循环链表

单-图1.png

单向循环.png

单向循环链表和单向链表只有一个差别,就是在普通单向链表中,尾节点(最后一个节点)的next指向的是NULL；而在单向循环链表中尾节点(最后一个节点)的next指向的是头结点(第一个节点)。

双向循环链表

双-图1.png

双向循环.png

双向循环链表和双向链表的区别与单向链表和单向循环链表的区别类似,就是在普通双向链表中,头节点(第一个节点)的prev和尾节点(最后一个节点)的next都是指向NULL；而在双向循环链表中头节点(第一个节点)的prev指向的是尾节点(最后一个节点)，尾节点(最后一个节点)的next指向的是头节点(第一个节点)。

注意：链表是可以有头结点(header)和尾节点(tial)，或者没有；或者只有头节点(header)，以下操作都是基于有header和tail节点的链表。

单链表操作原理以及核心代码

带头节点和尾节点的单链表

[图片上传失败...(image-576bdd-1603543710934)]

定义单链表节点Node

class Node<E> {
    E value;
    Node<E> next;

    public Node(E value) {
        this.value = value;
    }
}

添加节点

表头添加

单-图2.png
final Node<T> newNode = new Node<>(value);
if (header != null) {
    newNode.next = header;
}
header = newNode;
if (tail == null) {
    tail = header;
    header.next = tail;
    // tail.next = null; // 不组成循环
    tail.next = header; // 组成循环
}

表尾添加

单-图3.png
final Node<T> newNode = new Node<>(value);
final Node<T> temp = tail;
temp.next = newNode;
tail = newNode;

// tail.next = null; // 不组成循环
tail.next = header; // 组成循环

中间添加

单-图4.png
final Node<T> newNode = new Node<>(value);
final Node<T> nodeByIndex = getNodeByIndex(index - 1);
newNode.next = nodeByIndex.next;
nodeByIndex.next = newNode;

移除节点

移除表头

单-图5.png
header = header.next;
// tail.next = null; // 不组成循环
tail.next = header; // 组成循环

移除表尾

单-图6.png
Node<T> nodeByIndex = getNodeByIndex(size - 2);
Node<T> removeNode = nodeByIndex.next;
// nodeByIndex.next = null; // 不组成循环
nodeByIndex.next = header; // 组成循环

移除中间

单-图7.png
Node<T> removeNode = getNodeByIndex(index);
Node<T> removePre = getNodeByIndex(index - 1);
removePre.next = removeNode.next;

根据位置查询数据（节点）

参数index：需要查找的位置

private Node<T> getNodeByIndex(int index) {
    Node<T> node = header;
    for (int i = 0; i < index; i++) {
        node = node.next;
    }
    return node;
}

遍历

这里通过指针移动来直接打印节点数据

public void println() {
    System.out.println("----------------- 打印链表 ----------------- ");
    System.out.println("linked size: " + size);
    Node<T> node = header;
    for (int i = 0; i < size; i++) {
        System.out.println(node);
        node = node.next;
    }
}

size：表示链表的大小

双向链表操作原理以及核心代码

带头节点和尾节点的双向链表


双-图1.png

定义单链表节点Node

class Node<E> {
    E value;
    Node<E> prev;
    Node<E> next;

    public Node(E value) {
        this.value = value;
    }
}

添加节点

表头添加

双-图2.png
Node<T> newNode = new Node<>(value);
if (header != null) {
    newNode.next = header;
    header.prev = newNode;
}
header = newNode;

if (tail == null) {
    tail = header;
    tail.prev = header;
    header.next = tail;

    // 不组成循环
    // header.prev = null;
    // tail.next = null;

    // 组成循环
    header.prev = tail;
    tail.next = header;
}

表尾添加

双-图3.png
final Node<T> newNode = new Node<>(value);
final Node<T> temp = tail;
tail = newNode;
newNode.prev = temp;
temp.next = newNode;

// 不组成循环
// header.prev = null;
// tail.next = null;

// 组成循环
header.prev = tail;
tail.next = header;

中间添加

双-图4.png
Node<T> nodeByIndex = getNodeByIndex(index);
newNode.prev = nodeByIndex.prev;
newNode.next = nodeByIndex;
nodeByIndex.prev.next = newNode;
nodeByIndex.prev = newNode;

移除节点

移除表头

双-图5.png
final Node<T> temp = header;
header = header.next;
if (header != null) {
    // 不组成循环
    // header.prev = null;
    // tail.next = null;

    // 组成循环
    header.prev = tail;
    tail.next = header;
}

移除表尾

双-图6.png
final Node<T> temp = tail;
tail = tail.prev;
if (tail != null) {
    // 不组成循环
    // header.prev = null;
    // tail.next = null;

    // 组成循环
    header.prev = tail;
    tail.next = header;
}

移除中间

双-图7.png
Node<T> nodeByIndex = getNodeByIndex(index);
nodeByIndex.prev.next = nodeByIndex.next;
nodeByIndex.next.prev = nodeByIndex.prev;

根据位置查询数据（节点）

参数index：需要查找的位置

size：表示链表的大小

private Node<T> getNodeByIndex(int index) {
    if (index < (size >> 1)) {
        Node<T> node = header;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    } else {
        Node<T> node = tail;
        for (int i = size - 1; i > index; i--) {
            node = node.prev;
        }
        return node;
    }
}

遍历

这里通过指针移动来直接打印节点数据

public void println() {
    System.out.println("----------------- 打印链表 ----------------- ");
    System.out.println("linked size: " + size);
    Node<T> node = header;
    for (int i = 0; i < size; i++) {
        System.out.println(node);
        node = node.next;
    }
}

size：表示链表的大小

单向链表和双向链表的对比

单-图1.png
双-图1.png

  1. 删除单链表中的某个结点时，一定要得到待删除结点的前驱，得到该前驱有两种方法，第一种方法是在定位待删除结点的同时一路保存当前结点的前驱。第二种方法是在定位到待删除结点之后，重新从单链表表头开始来定位前驱。但其实这两种方法的效率是一样的，指针的总的移动操作都会有2*i次。而如果用双向链表，则不需要定位前驱结点。因此指针总的移动操作为i次。

  2. 查找时也一样，我们可以借用二分法的思路，从head（首节点）向后查找操作和last（尾节点）向前查找操作同步进行，这样双链表的效率可以提高一倍。

  3. 从存储结构来看，每个双链表的节点要比单链表的节点多一个指针，而长度为n就需要 n*length（length表示指针所需要的内存空间大小） 的空间。

完整代码实现及测试(java)

单向链表实现：SingleLinkedList.java

双向链表实现：DoubleLinkedList.java

测试代码：LikedListTest.java

接下文《数据结构——链表（二）》

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