【Java数据结构】LinkedList-链表

简介: 本文章将以模拟Java集合类LinkedList的模式去研究链表

Java数据结构 & LinkedList & 链表

本文章将以模拟Java集合类LinkedList的模式去研究链表

在另一篇文章中将结合本章节学到的知识去解决一些笔试中遇到的难题 ^ v ^

这些题,我将写一篇博客,大家可以去看一下加深一下对链表的理解

学完这些入门题后,大家也可以去刷牛客或者力扣咯😊

链表背景知识

在顺序表中,每个元素在内存中都是紧密排在一起的


而在一些操作中,挪动元素成为一个很频繁的操作

并且扩容这一操作也相对频繁

为了解决上述顺序表的不足,链表牺牲了下标访问的速率,做出一下改变


value值存在一个“引用”中,我们称为“节点”

这个“节点”有两个最基本的属性

value

下一个节点的引用—后驱

则链表的空间排布就是链式的,并不是紧密排列的【下列引用地址是随便写的】

对应的性质随后就讲,但是不难发现,如果这样下去,插入元素的效率很高,且不需要扩容不需要大规模的挪动

但是也失去了快速下标访问的能力~


1. LinkedList链表的模拟

记住 java的一个性质:当一个引用无法再次访问到(java不支持地址直接访问),那么这个引用将自动被 jvm收回

那么一个链表的头节点(第一个有效数据的节点引用)必须有一个引用指向它,不然整个链表就会被回收

※重点说明:下面模拟的是单向不带头不循环链表~

1. 1 MyLinkedList 基础摸版

注意:Java的集合类LinkedList是双向不带头不循环链表

这儿我首先讲单向链表,最后再进行修改!

并且在链表面试题那里,我将讲解更加复杂的链表

我们将整个链表和其相关法打包在一个类中,只需要实例化这个类就可以使用啦

链表类型(2 * 2 * 2 = 8种)

链表类型当然有更多,而那些是oj题,在文章的最后我会提供链表oj题的链接~


带or不带头:就是有没有一个没有value的带头节点(这个节点的后继才是第一个有效数据的节点引用)


循环or不循环:即在链表的尾部的后继指向前面的节点引用或者本身


双向or单向:每一个节点不只有后继,还有前继


总览,细节解说在其后~

public class MyLinkedList {
    private int size;
    Node head;
    @Override
    public String toString() {
        return "MyLinkedList{" +
                " " + size +
                ", " + head +
                '}';
    }
    public MyLinkedList(MyLinkedList myLinkedList) {
    }
    public MyLinkedList(int date) {
    }
    public MyLinkedList() {
    }
    public class Node {
    }
    public void addFirst(int data) {
    }
    public void display() {
    }
    public void display(Node head) {
    }
    public void addLast(int data) {
    }
    public void addIndex(int index,int data) {
    }
    private void checkIndex(int index, String str) {
    }
    public Node getNode(int index) {
    }
    private Node searchPreviousOne(int index) {
    }
    private Node searchPreviousOne(Integer val) {
    }
    public boolean contains(int key) {
    }
    public void remove(int key) {
    }
    public void removeAllKey(int key) {
    }
    public int size() {
    }
    public void clear() {
    }
}


节点类型(静态内部类)


public static class Node {
    private int value;
    Node next;
    @Override
    public String toString() {
        return "{" +
                " " + value +
                ", " + next +
                '}';
    }
    public Node(int value) {
        this.value = value;
    }
}


值 + 后继(单向链表)

下标非法对应的异常


这个异常在后续传下标为参数的时候,非法下标访问则会被抛出~

public class IndexOutOfException extends RuntimeException{
    public IndexOutOfException() {
    }
    public IndexOutOfException(String message) {
        super(message);
    }
}


1.2 MyLinkedList基础属性

size:已插入元素的个数

每插入一个数据,size++,每删除一个数据,size–

牺牲空间,提高获取链表大小方法的效率~

head:头部节点引用(第一个有效节点)

这个节点不是“哨兵头”,而是一个有效的节点

private int size;


Node head;


1.3 MyLinkedList基础功能

即顺序表有的都应该有

因为一般都去实现List类,所以用到的方法都是一样的

这也体现了普通类实例化接口的方式的好处:这样建立的对象功能更加具体(少且精)

只是一个用顺序表实现,一个由链表实现罢了

1.3.1 构造方法

public MyLinkedList(int date) {

   this.head = new Node(date);

}


public MyLinkedList() {


}


不带参数的构造方法

head为null(默认值)

带参数的构造方法

插入第一个数据,head不为null

1.3.2 增加元素

1.3.2.1 头插法

public void addFirst(int data) {
    Node first = new Node(data);
    first.next = head;
    head = first;
    size++;
}


实例化一个新节点

这个新节点的后继“链接”到head(原链表的头)

头节点引用指向新节点

有效数据个数加一

如果head为null,并不影响


1.3.2.2 尾插法

public void addLast(int data) {
    if(head == null) {
        head = new Node(data);
        size++;
        return;
    }
    Node cur = head;
    while(cur.next != null) {
        cur = cur.next;
    }
    cur.next = new Node(data);
    size++;
}

由于head可能为null,而这是有影响的,所以要分情况处理


head为null,实例化一个新节点,这个新节点成为head


head不为null, 定义一个临时的引用代替head(防止链表被回收)==》cur,


【current—电流—链式访问】


到达最后一个节点,而不是cur为空


cur的后继链接新实例化的新节点


有效数据个数加一


1.3.2.3 随机插入

public void addIndex(int index,int data) {
    //下标判断
    try {
        checkIndex(index, "Exception from addIndex(...)");
    } catch (IndexOutOfException e) {//catch后jvm解决不了
        e.printStackTrace();
        return;
    }
    Node cur = head;
    Node newOne = new Node(data);
    if(index == 0) {
        addFirst(data);
        return;
    }
    //到达index的前一个节点
    while(--index != 0) {
        cur = cur.next;
    }
    newOne.next = cur.next;
    cur.next = newOne;
    size++;
}
private void checkIndex(int index, String str) {
    if(index < 0 || index > size) {
        throw new IndexOutOfException(str);
    }
}

进行下标判断,调用方法:checkIndex()去检测下标是否合理

用刚才的cur替身,移动到index的前一个节点

如果index为0,则为头插+return;

index合理且不为0,则存在index前一个节点

到达对应位置后,用新实例化的新节点记录下对应位置的节点的后继(防止链表被回收)

对应位置的节点的后继为新节点

有效数据个数加一


1.3.3 打印方法

public void display() {
    Node cur = head;
    System.out.print("[ ");
    while(cur != null) {
        System.out.print(cur.value + " ");
        cur = cur.next;
    }System.out.println("]");
}
public void display(Node head) {
    Node cur = head;
    System.out.print("[ ");
    while(cur != null) {
        System.out.print(cur.value + " ");
        cur = cur.next;
    }System.out.println("]");
}

从头开始打印

从指定节点开始打印

1.3.4 获取部分链方法

public Node getNode(int index) {
    try {
        checkIndex(index, "Exception from getNode(...)");
        Node cur = head;
        while(index-- != 0) {
            cur = cur.next;
        }
        return cur;
    } catch (IndexOutOfException e) {
        e.printStackTrace();
        return null;
    }
}

判断下标是否合理

走到index的位置,返回对应节点

依据这个节点获取部分链表

此部分链表就是以主链表其中节点为head的子链表~


1.3.5 查找方法

–找到值是返回节点引用而不是下标

书写链表时, 空指针异常是经常发生的,所以要很小心 ,有很多细节也要去小心

private Node searchPreviousOne(int index) {
    try {
        checkIndex(index, "Exception from searchPreviousOne(...)");
    } catch (IndexOutOfException e) {
        e.printStackTrace();
        return null;
    }
    if(index == 0) {
        return null;
    }
    Node cur = head;
    while(--index != 0) {
        cur = cur.next;
    }
    return cur;
}
private Node searchPreviousOne(Integer val) {//区分下标用Integer,触发重载
    int value = val.intValue();
    if (value == head.value || head == null) {
        return null;
    } else {
        Node cur = head;
        while (cur.next != null) {
            if (cur.next.value == value) {
                return cur;
            } else {
                cur = cur.next;
            }
        }
    }
    return null;
}
//遍历链表查看是否存在键值~~~
public boolean contains(int key) {
    if(head != null) {
        Node cur = head;
        while(cur != null) {
            if(cur.value == key) {
                return true;
            }else {
                cur = cur.next;
            }
        }
    }
    return false;
}

规定


当传入的参数是int型 =》 代表下标,找到下标前的一个节点


判断下标是否合理,合理就找,第一个节点前也是null ~

当传入的参数是Integer型 =》 代表值,找的第一个这个值前的一个节点~


空链表返回null,第一个节点前面也是null~

遍历链表,检测节点的后一个节点的值是否是那个键值~

找不到返回也null~

contains() 方法则是遍历整个链表,找到了返回true,找不到返回false~


1.3.5.1 图解1


1.3.5.2 图解2


1.3.5.3 图解3


1.3.6 删除方法

删除方法也很可能出现空指针异常,所以要加倍小心~

public void remove(int key) {
    if(contains(key)) {
        size--;
        if(head.value == key) {
            head = head.next;
        }else {
            Node prev = searchPreviousOne(Integer.valueOf(key));//传入Integer
            prev.next = prev.next.next;
        }
    }
}


删除一个节点很简单

这个节点是从前往后数的第一个对应键值的节点~

首先,判断链表中有没有这个键值~

存在的话这个节点是必然要删除的

如果是首节点,head直接往后走一次,该节点被删除

调用searchPreviousOne,找到前一个节点,然后让这个prev的后驱指向此节点的后驱(跳跃式忽视这个节点)

这样就没有任何对象指向这个节点,那么这个节点就会被回收~


public void removeAllKey(int key) {
    if(head == null) {
        return;
    }
    Node prev = head;
    Node cur = head.next;
    while(cur != null) {
        if(cur.value == key) {
            size--;
            prev.next = cur.next;
        }else {
            prev = cur;
        }cur = cur.next;
    }
    if(head.value == key) {
        size--;
        head = head.next;
    }
}

删除所有同键值节点~


重难点,细细理解~


这个稍微复杂,思想仍然是(跳跃式忽视节点的方法)

用到了一个前后指针的算法

prev一开始处于head的位置,cur在head.next的位置

遍历链表,结束条件是cur为null

正常情况下,即删除节点之前,prev和cur都是同步走的

但cur遇到要删除的节点的时候,要让cur去找下一个非此键值的节点(如果还是该键值,这个节点将不会被后续操作删除)或者null,cur每次遇到键值匹配的节点,size–

cur每次找到key,prev的后驱指向cur的后驱 ===》实现删除连续节点

cur一旦找不到key,prev就会继承cur的位置

最不应该忘记的是这个:

头节点留到最后再判断,如果一开始将头结点删了,那么后续仍然有头结点无法被判断,反反复复无法解决问题~,这样还不如先判断后面的节点,最后再判断头节点

如果头节点该删,head = head.next~

动图演示:



1.3.7 获取链表大小即清空链表~

    public int size() {
        return this.size;
    }
    public void clear() {
        head = null;
        size = 0;
    }

1


清空单向链表,只需要让head为null,引发连锁反应,全部收回~

2. 双向链表的LinkedList

系统类LinkedList,本质上是一个双向链表

它改进了单链表的缺陷,就是只要流动过去,是没法找前一个节点的~

这很不方便~

所以它又牺牲了空间,换取时间~

下面我将讲解依此改进后的MyLinkedList,并不是完全模拟LinkedList的高级操作,但是有借鉴~


2.1 改进后的属性

总览,细节在后~

public class MyLinkedList{
    private int size;
    Node head;
    Node last;
    @Override
    public String toString() {
        return "MyLinkedList{" +
                " " + size +
                ", " + head +
                '}';
    }
    public MyLinkedList() {
    }
    public static class Node{
        private int value;
        Node next;
        Node prev;
        @Override
        public String toString() {
            return "{" +
                    " " + value +
                    ", " + next +
                    '}';
        }
        public Node(int value) {
            this.value = value;
        }
        public int getValue() {
            return value;
        }
        public void setValue(int value) {
            this.value = value;
        }
    }
}

2.1.1 改动1

Node head;

Node last;


不仅提供了头节点,还提供了尾节点


这两个节点都是有效节点~

尾节点就相当于,逆向链表的头节点


尾节点的存在,我们尾插的时间复杂度就相当于O(1)


2.1.2 改动2

public static class Node{
    private int value;
    Node next;
    Node prev;
    @Override
    public String toString() {
        return "{" +
                " " + value +
                ", " + next +
                '}';
    }
    public Node(int value) {
        this.value = value;
    }
    public int getValue() {
        return value;
    }
    public void setValue(int value) {
        this.value = value;
    }
}

提供了前驱~

这样cur探路的时候,即能后退,又能前进~

封装了value

提供getter 和 setter~

后续别的类需要访问value的都得改为get方法~

需要改动的要改为set方法~

2.2 改进后的方法

2.2.1 改进后的插入方法们~

总览,后面细节分析~

public void addFirst(int data) {
    size++;
    Node newOne = new Node(data);
    if(head == null) {
        last = newOne;
        head = newOne;
    }else {
        newOne.next = head;
        head.prev = newOne;
        head = newOne;
    }
}
public void addLast(int data) {
    size++;
    Node newOne = new Node(data);
    if(last == null) {
        head = newOne;
        last = newOne;
    }else {
        newOne.prev = last;
        last.next = newOne;
        last = newOne;
    }
}
public void addIndex(int index,int data) {
    try {
        checkIndex(index, "Exception from addIndex(...)");
    } catch (IndexOutOfException e) {
        e.printStackTrace();
        return;
    }
    Node cur = head;
    Node newOne = new Node(data);
    if(index == 0) {
        addFirst(data);
    }else if(index == size) {
        addLast(data);
    }else {
        while(index-- != 0) { // --index 是因为那个单链表找不到前一个节点
            cur = cur.next;
        }
        newOne.next = cur;
        newOne.prev = cur.prev;
        cur.prev.next = newOne;
        cur.prev = newOne;
        size++;
    }
}

头插法,也是last的尾插法~,所以要判断head是否为null ~


尾插法,也是last的头插法,这次要借助last~

基本跟头插法是一样的,同构~


下标插入,稍微复杂的链接操作~


动图演示:


我们需要将新节点的“两端前驱后继”链接到对应位置~

记录下来,发过来的话,那个节点就会被回收,链表操作这个是要注意的~


2.2.2 改进后的删除

总览,后面细节分析~

public void remove(int key) {
    Node cur = head;
    while(cur != null) {
        if(cur.value == key) {
            if(cur == head) {
                cur.next.prev = null;
                head = head.next;
            }else if (cur == last) {
                cur.prev.next = null;
                last = last.prev;
            }else {
                cur.prev.next = cur.next;
                cur.next.prev = cur.prev;
            }
            size--;
            return;
        }
        cur = cur.next;
    }
}
public void removeAllKey(int key) {
    Node cur = head;
    while(cur != null) {
        if(cur.value == key) {
            if(cur == head) {
                cur.next.prev = null;
                head = head.next;
            }else if (cur == last) {
                cur.prev.next = null;
                last = last.prev;
            }else {
                cur.prev.next = cur.next;
                cur.next.prev = cur.prev;
            }
            size--;
        }
        cur = cur.next;
    }
}


2.2.2.1 删除从左到右第一个key


动图演示:


2.2.2.2 删除全部key节点~

更上面那个删除单一点找不同~

不同就是,只需要把那个循环内的return删掉就OK了~


2.2.3 改动后的清空方法

public void clear() {
    size = 0;
    while(head != null) {
        head = head.next;
        if(head == null) {
            last = null;
            return;
        }
        head.prev = null;
    }
}

我通过一些工具检测到,直接置head为null也可以回收这些节点

这样很好想,因为head都为null了,起了连锁反应,后面的节点都没办法访问到

所以都被回收~

我的这个方法也可以,巧妙地让每一个cur走到的节点的前节点恰好被回收~

清空方法在LinkedList源码中,是一个一个节点的将一些前驱后驱置为null

一个个的清


3. 测试

这里不带大家演示LinkedList的使用了


这跟顺序表ArrayList的使用在这一方面是完全一样的~

public static void main(String[] args) {
    MyLinkedList myLinkedList = new MyLinkedList();
    System.out.println(myLinkedList.size());
    myLinkedList.addLast(155);
    System.out.println(myLinkedList.size());
    myLinkedList.addLast(15);
    System.out.println(myLinkedList.size());
    myLinkedList.addFirst(166);
    System.out.println(myLinkedList.size());
    myLinkedList.addFirst(16);
    System.out.println(myLinkedList.size());
    myLinkedList.addIndex(0, 6);
    System.out.println(myLinkedList.size());
    myLinkedList.addIndex(5, 5);
    myLinkedList.addIndex(1, 7);
    myLinkedList.display();
    System.out.println("=================");
    myLinkedList.clear();
    myLinkedList.addLast(155);
    myLinkedList.addLast(15);
    myLinkedList.addFirst(166);
    myLinkedList.addFirst(16);
    myLinkedList.addIndex(0, 6);
    myLinkedList.addIndex(5, 5);
    myLinkedList.addIndex(1, 7);
    myLinkedList.remove(15);
    myLinkedList.remove(166);
    System.out.println(myLinkedList);
    myLinkedList.clear();
    System.out.println("================");
    myLinkedList.addFirst(55);
    myLinkedList.addFirst(55);
    myLinkedList.addFirst(55);
    myLinkedList.addIndex(2, 555);
    myLinkedList.removeAllKey(55);
    myLinkedList.display();
    System.out.println(myLinkedList.contains(555));
    System.out.println(myLinkedList.contains(55));
}



测试结果正常~

s:103
+关注
目录
打赏
0
0
0
0
34
分享
相关文章
|
5月前
|
Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。
【10月更文挑战第19天】本文详细介绍了Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。HashMap以其高效的插入、查找和删除操作著称,而TreeMap则擅长于保持元素的自然排序或自定义排序,两者各具优势,适用于不同的开发场景。
67 1
|
5月前
|
告别混乱!用Java Map优雅管理你的数据结构
【10月更文挑战第17天】在软件开发中,随着项目复杂度增加,数据结构的组织和管理至关重要。Java中的Map接口提供了一种优雅的解决方案,帮助我们高效、清晰地管理数据。本文通过在线购物平台的案例,展示了Map在商品管理、用户管理和订单管理中的具体应用,有效提升了代码质量和维护性。
118 2
Java 集合江湖:底层数据结构的大揭秘!
小米是一位热爱技术分享的程序员,本文详细解析了Java面试中常见的List、Set、Map的区别。不仅介绍了它们的基本特性和实现类,还深入探讨了各自的使用场景和面试技巧,帮助读者更好地理解和应对相关问题。
67 5
本文聚焦于Java内存管理与调优,介绍Java内存模型、内存泄漏检测与预防、高效字符串拼接、数据结构优化及垃圾回收机制
在现代软件开发中,性能优化至关重要。本文聚焦于Java内存管理与调优,介绍Java内存模型、内存泄漏检测与预防、高效字符串拼接、数据结构优化及垃圾回收机制。通过调整垃圾回收器参数、优化堆大小与布局、使用对象池和缓存技术,开发者可显著提升应用性能和稳定性。
79 6
Java中的数据结构:ArrayList和LinkedList的比较
【10月更文挑战第28天】在Java编程世界中,数据结构是构建复杂程序的基石。本文将深入探讨两种常用的数据结构:ArrayList和LinkedList,通过直观的比喻和实例分析,揭示它们各自的优势与局限,帮助你在面对不同的编程挑战时做出明智的选择。
Java 中常用的数据结构
【10月更文挑战第20天】这些数据结构在 Java 编程中都有着广泛的应用,掌握它们的特点和用法对于提高编程能力和解决实际问题非常重要。
65 6
Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效
【10月更文挑战第19天】在软件开发中,随着项目复杂度的增加,数据结构的组织和管理变得至关重要。Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效。本文通过在线购物平台的案例,展示了Map在商品管理、用户管理和订单管理中的具体应用,帮助开发者告别混乱,提升代码质量。
51 1
|
4月前
|
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
387 9
|
4月前
|
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
64 1
|
2月前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
159 77

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等