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)); }
测试结果正常~
