数据结构-LinkedList

一 链表概述

链表是一种线性表，实际上是由节点（Node）组成的，一个链表拥有不定数量的节点。其数据在内存中存储是不连续的，它存储的数据分散在内存中，每个结点只能也只有它能知道下一个结点的存储位置。由N各节点（Node）组成链表，每一个Node记录本Node的数据及下一个Node。向外暴露的只有一个头节点（Head），我们对链表的所有操作，都是直接或者间接地通过其头节点来进行的。

二 为什么链表这么重要

1⃣️ 链表是一种真正意义上的动态数据结构；
2⃣️ 链表是最基础最简单的动态数据结构，熟练的掌握链表可以在后续学习更加高级的数据结构打下基础；
3⃣️ 学习链表可以更加深刻的理解指针的概念；
4⃣️ 更加深入的理解递归；
5⃣️ 链表可以辅助组成更加高级的数据结构，比如说图结构等；

三 链表结构图示

链表数据结构图示

优点：真正的动态不需要处理固定容量的问题；
缺点：丧失的随机访问的能力；

四 链表和数组对比

1⃣️ 数组最好适用于索引有语意的情况，最大的优点是支持快速查询；
2⃣️ 链表不适合用于索引有语意的情况，最大的优点是动态；

五 链表的简单实现

package com.mufeng.linkedList;

/**
 * Created by wb-yxk397023 on 2018/6/19.
 */
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);
        }

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

六 在链表中添加元素

1⃣️ 上边有说过：向外暴露的只有一个头节点（Head），我们对链表的所有操作，都是直接或者间接地通过其头节点来进行的；所以完整的数据结构图示应该是这样的
链表的完整数据结构图示

2⃣️ 简单的代码实现

package com.mufeng.linkedList;

/**
 * Created by wb-yxk397023 on 2018/6/19.
 */
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);
        }

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

    // 链表头元素
    private Node head;
    // 链表元素个数
    private int size;

    // 构造函数
    public LinkedList(){
        // 默认初始值为null
        head = null;
        // 默认元素个数为0
        size = 0;
    }

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

    // 判断链表是否为空
    public boolean isEmpty(){
        return size == 0;
    }
}

3⃣️ 向链表中添加元素，当我们操作向数组中添加元素的时候我们实际操作的是向数组尾部添加元素，因为向数组尾部添加元素是最方便的，因为在数组中我们有维护一个size，这个size属性追踪的是数组的尾部，所以说我们在为数组添加元素的时候向数组尾部添加是最方便的；而对于链表则是完全相反的，链表添加元素的时候向头部添加是最方便的，因为在链表中我们有维护一个head的属性，这个属性表示链表的头部，所以在向链表中添加元素是与数组恰恰相反的；

4⃣️ 在链表头添加元素图示（链表添加元素的关键在于怎么把一个数据添加到现有的结构中同时又不会破坏现有的结构）
创建一个新的node
改变node中next的指向，让其指向head
紧接着让head指向node
完成元素添加操作
删除node块作用域

5⃣️ 代码实现

// 在链表头添加新的元素e
    public void addFrist(E e){
        // 声明一个新的node作用域
        Node node = new Node(e);
        // 改变node中next的指向，让其指向head
        node.next = head;
        // 让head指向node
        head = node;

        // 可以简写为：head = new Node(e, head)
        // 维护size
        size++;
    }

6⃣️ 在链表中间添加新的元素图示（在链表“索引”为2的位置添加元素，链表没有索引在这里只是借助索引的概念来方便理解）
创建新的node节点
找到新node节点之前的节点prev
通过遍历找到需要插入的那个节点的上一个节点prev
将node的next指向prev的next，改变原有的指向关系
将prev的next等于node，改变指向关系
完成向链表中间插入数据的操作
这个操作的关键点在于需要找到要添加的节点的前一个节点；另外指向关系的顺序是固定的，加入顺序发生了变化的话就会变成下边这样：
指向顺序变化后的错误演示
所以说在操作链表的时候顺序非常重要，如果颠倒顺序的话结果有可能就是错误的。

7⃣️ 代码实现

// 在链表的index(0-based)位置添加新的元素e(此功能不常用)
    public void add(E e, int index){
        // 判断index是否合法
        if (index < 0 || index > size){
            throw new IllegalArgumentException("Add failed. Illegal index.");
        }
        // 判断是否是在链表头进行添加操作
        if (index == 0){
            addFrist(e);
        }else {// 如果不是在链表头进行添加操作就执行这个逻辑
            // 声明prev属性，用来标示需要添加的节点的前一个节点
            Node prev = head;
            // 通过遍历找到要添加节点的前一个节点
            for (int i = 0; i < index - 1; i++){
                prev = prev.next;
            }
            // 创建新的node节点
            Node node = new Node(e);
            // 改变指向，将新的元素指向prev的下一个元素
            node.next = prev.next;
            // 改变指向，将prev.next的指针指向node
            prev.next = node;

            // 可以简写为 prev.next = new Node(e, prev.next)
            
            // 维护size属性
            size++;
        }
    }

8⃣️ 向链表的尾部添加元素代码实现

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

六 使用链表的虚拟头节点

1⃣️ 为链表设置虚拟头节点

背景：在上边第七步中由于我们需要对是否在链表头部增加元素进行特殊的处理，所以接下来我们需要引入一个新的概念——链表中的虚拟头节点；
解决思路：为链遍头增加一个虚拟节点，这个节点不存储真实数据，如图所示
链表头虚拟节点图示
代码演示
   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);
        }

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

    // 链表头元素
    private Node dummyHead;
    // 链表元素个数
    private int size;

    // 构造函数
    public LinkedList(){
        // 默认初始值为null
        dummyHead = new Node();
        // 默认元素个数为0
        size = 0;
    }

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

    // 判断链表是否为空
    public boolean isEmpty(){
        return size == 0;
    }

    // 在链表头添加新的元素e
    public void addFrist(E e){
        add(e,0);
    }

    // 在链表的index(0-based)位置添加新的元素e(此功能不常用)
    public void add(E e, int index){
        // 判断index是否合法
        if (index < 0 || index > size){
            throw new IllegalArgumentException("Add failed. Illegal index.");
        }

        Node prev = dummyHead;
        // 通过遍历找到要添加节点的前一个节点
        for (int i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
//        // 创建新的node节点
//        Node node = new Node(e);
//        // 改变指向，将新的元素指向prev的下一个元素
//        node.next = prev.next;
//        // 改变指向，将prev.next的指针指向node
//        prev.next = node;

        prev.next = new Node(e, prev.next)

        // 维护size属性
        size++;

    }

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

七 链表的遍历 查询和修改

1⃣️ 链表的遍历

/**
     * 获得链表的第index(0-based)个位置的元素,在链表中不是一个常用的操作.
     * @param index
     * @return
     */
    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;
    }

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

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

2⃣️ 链表的更新操作

/**
     * 修改链表的第index(0-based)个位置的元素为e,在链表中不是一个常用的操作.
     * @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;
    }

3⃣️ 链表查询包含元素

/**
     * 查询链表中是否存在元素e
     * @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;
    }

4⃣️ 重写toString

/**
     * toString
     * @return
     */
    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        Node cur = dummyHead.next;

        while (cur != null){
            res.append(cur + "->");
            cur = cur.next;
        }
        res.append("null");
        return res.toString();
    }

5⃣️ 测试

package com.mufeng;

import com.mufeng.linkedList.LinkedList;

public class Main {

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

        for (int i = 0; i < 5; i++) {
            linkedList.addFrist(i);
            System.out.println(linkedList);
        }

        linkedList.add(666, 2);
        System.out.println(linkedList);
    }
}
测试结果

八 从链表中删除元素

1⃣️ 删除操作图书
声明一个带有虚拟头节点的链表
声明prev代表要删除的node的前一个节点
声明一个delNode元素代表要被删除的节点
将prev.next指向delNode.next
将delNode.next指向null

2⃣️ 代码实现

/**
     * 从链表中删除index(0-based)位置的元素, 返回删除的元素(在链表中不是一个常用的操作)
     * @param index
     * @return
     */
    public E remove(int index){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed. Index is illegal.");

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

3⃣️ 完善其他删除逻辑

/**
     * 从链表中删除第一个元素
     * @return
     */
    public E removeFrist(){
        return remove(0);
    }

    /**
     * 从链表中删除最后一个元素
     * @return
     */
    public E removeLast(){
        return remove(size - 1);
    }

4⃣️ 测试代码

package com.mufeng;

import com.mufeng.linkedList.LinkedList;

public class Main {

    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < 5; i++) {
            linkedList.addFrist(i);
            System.out.println(linkedList);
        }
        linkedList.add(666, 2);
        System.out.println(linkedList);
        
        linkedList.remove(2);
        System.out.println(linkedList);
        linkedList.removeFrist();
        System.out.println(linkedList);
        linkedList.removeLast();
        System.out.println(linkedList);
    }
}
测试结果

九 使用链表实现栈

1⃣️ 代码实现以及自测

package com.mufeng.stacks;

import com.mufeng.linkedList.LinkedList;

/**
 * Created by wb-yxk397023 on 2018/6/22.
 */
public class LinkedListStack<E> implements Stack<E> {

    private LinkedList<E> list;

    public LinkedListStack(){
        list = new LinkedList<>();
    }
    @Override
    public int getSize() {
        return list.getSize();
    }

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

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

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

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

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

    /**
     * 链表栈自测
     * @param args
     */
    public static void main(String[] args) {

        LinkedListStack<Integer> stack = new LinkedListStack<>();

        for(int i = 0 ; i < 5 ; i ++){
            stack.push(i);
            System.out.println(stack);
        }

        stack.pop();
        System.out.println(stack);
    }
}
测试结果

十 使用链表实现队列

1⃣️ 链表实现队列图示

参考数组实现队列的原理，链表实现队列也需要对现有的链表进行改进，如下所示
现有的链表结构
由于有head元素的存在帮助我们标记链表头的位置，可以让我们对链表头操作变的非常方便，但是队列是一个有首有尾的结构，所以我们也需要对链表的尾部进行操作，所以需要对现有的链表进行改造，如下所示
增加tail元素用来标记链表尾部
由于在链表中删除节点需要先找到待删除节点的，所以对于尾部节点tail来说删除元素并没有tail头部节点操作起来方便，无法使用O(1)的复杂度来删除tail位置的节点，但是操作添加节点是可以使用O(1)复杂度实现的，所以我们需要将head作为对首，tail作为队尾！
链表队列图示
由于队列不会对中间节点直接进行操作，所以链表实现的队列就没有添加虚拟头节点的必要了；但是需要注意链表为空的情况，如图所示
链表为空的情况

2⃣️ 代码实现以及测试

package com.mufeng.queues;

/**
 * Created by wb-yxk397023 on 2018/6/23.
 */
public class LinkedListQueues<E> implements Queues<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, tail;
    private int size;

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

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

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

    @Override
    public void enqueues(E e) {
        if (tail == null){
            tail = new Node(e);
            head = tail;
        }else {
            tail.next = new Node(e);
            tail = tail.next;
        }
        size++;
    }

    @Override
    public E dequeues() {
        if(isEmpty()) {
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
        }

        Node retNode = head;
        head = head.next;
        retNode.next = null;

        if (head == null){
            tail = null;
        }

        size--;
        return retNode.e;
    }

    @Override
    public E getFront() {
        if(isEmpty()) {
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
        }

        return head.e;
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("Queue: front ");

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

    public static void main(String[] args){

        LinkedListQueues<Integer> queue = new LinkedListQueues<>();
        for(int i = 0 ; i < 10 ; i ++){
            queue.enqueues(i);
            System.out.println(queue);

            if(i % 3 == 2){
                queue.dequeues();
                System.out.println(queue);
            }
        }
    }

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

推荐阅读更多精彩内容