玩转数据结构之链表
0. 序列
之前有一篇文章讲解了“动态数组”，以及通过这个“动态数组”实现了栈和队列，而这里的“动态数组”的底层其实依靠的是静态数组，只是靠resize解决固定容量的问题。而今天所要讲解的“链表”数据结构，它是真正的动态数据结构。
链表也属于线性表（不了解线性表概念的，可点击跳转阅读https://www.jianshu.com/p/efa6a9d3a975），由于其在内存中的空间分配是不连续的，所以它是动态数据结构。
这篇文章我们讲解链表的添加、查询、遍历、删除操作。
1. 简介
链表简介
① 链表将数据存储在“节点”（Node）中
② e 就是我们存放数据的类型，next 相当于一个指针，指向下一个存储数据的节点
③ 节点的next 指针指向null，表明这是最后一个节点。
2. 特点
- 优点：
① 插入和删除数据相当方便，不需要移动大量数据。
② 内存分配发生在运行时期，不需要事先声明可能占用的最大的内存空间，能够充分节省内存。 - 缺点：
① 设计时较为麻烦。
② 查找和修改数据必须按顺序找到数据为止，即丧失了随机访问的能力。
3. 数组和链表的对比
- 数组
- 数组最好用于索引有语意的情况。
- 最大的优点：支持快速查询修改
- 链表
- 链表不适合用于索引有语意的情况
- 最大的优点：支持快速插入和删除
4. 定义一个链表的节点
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);
}
@Override
public String toString() {
return e.toString();
}
}
private Node head; // 1. 指向第一个节点
private int size; // 2. 记录元素个数
public int getSize() {
return size;
}
// 3. 初始化链表的时候 链表的头部为null
public LinkedList() {
head = null;
size = 0;
}
// 4. 返回链表是否为空
public boolean isEmpty() {
return size == 0;
}
}
① 代码 1 ：定义变量head，指向第一个Node节点
② 代码 2 ：记录元素的个数
③ 代码 3 ：初始化链表的时候，链表元素数量为0，头部节点指向null。
④ 代码 4 ：当元素的个数为0的时候，证明链表是空的。
5. 添加元素
-
在链表头添加新的元素e
如果是数组，向尾部添加元素比较方便，因为是静态的数据结构，在内存中的空间分配是连续的，记录下size，即tail == size，tail指向的位置就是下一个为数组开辟的空间。
如果是链表，因为我们知道永远知道第一个元素的位置，即head指针所指向的内存空间。所以链表向首部添加元素比较方便，只需要让需要添加的元素的next指针指向原来的第一个元素节点，然后移动下head指针的指向就可以了，如图所示：
链表首部添加元素
public void addFirst(E e){
/**
* Node node = new Node(e);
* node.next = head;
* head = node;
*/
head = new Node(e,head); // 代码1
size ++;
}
代码1相当于注释中的两句话，无非是把元素e传入，并且把next指针指向下一个节点，然后再把这个head指针指向新添加的Node节点。
-
在链表中间添加元素
添加元素到链表中间位置
既然节点之间的链接是通过指针next来链接的，那如果我想添加节点数据为666的数据到节点数据为1和2的节点中间的位置，那么我只需要找到要添加的节点的前一个节点。我们指定这个节点是prev。此时，我们让想插入的节点的指针next指向prev节点指向的节点，然后让prev节点的指针next指向新添加的节点即可。
// 在链表的index位置添加新的元素e
// 在链表中不是一个常用的操作，练习用：
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed. Illegal index.");
}
if (index == 0)
addFirst(e);
else {
Node prev = head;
for (int i = 0; i < index - 1; i++)
prev = prev.next;
// Node node = new Node(e);
// node.next = prev.next;
// prev.next = node;
prev.next = new Node(e, prev.next);
size++;
}
}
① 引入了一个概念索引index，假设我们把第一个节点当做索引0，最后一个节点当作索引size -1 ，这样插入的时候就能和数组一样，插入到我们想要插入的位置。
② 这里首先判断index的合法性，最小0，最大size，然后判断下当index == 0 的时候调用addFirst方法即可，插入到链表中间和末尾的时候就可以执行下面的逻辑：找到要插入的位置的前一个节点prev即可。
- 向链表末尾添加元素
// 在链表末尾添加新的元素e
public void addLast(E e) {
add(size, e);
}
6. 设立虚拟头节点
在上一小节我们发现，当插入元素的位置为0的时候，我们需要进行特殊处理，因为我们添加元素的方法是找到要添加元素的位置的前一个节点prev，而索引为0的节点并没有前一个节点，所以这里我们为链表设立一个虚拟头节点。
虚拟头节点
我们把这个虚拟头节点称为dummyHead，它存储的元素是null，对调用者来说是没有意义的，但是对逻辑非常有意义，和循环队列浪费一个空间的设计意义相同。下面我们修改下相关代码：
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);
}
@Override
public String toString() {
return e.toString();
}
}
private Node dummyHead; // 1. 指向第一个节点
private int size; // 2. 记录元素个数
public int getSize() {
return size;
}
// 3. 初始化链表的时候 链表的头部为null
public LinkedList() {
dummyHead = new Node(); // 5.链表初始化
size = 0;
}
// 4. 返回链表是否为空
public boolean isEmpty() {
return size == 0;
}
// 在链表的index位置添加新的元素e
// 在链表中不是一个常用的操作，练习用：
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed. Illegal index.");
}
Node prev = dummyHead;
for (int i = 0; i < index; i++) // 6. 前面添加了一个虚拟头节点，这里index-1 修改为index，即多执行一个循环
prev = prev.next;
prev.next = new Node(e, prev.next);
size++;
}
// 在链表头添加新的元素e
public void addFirst(E e) {
add(0, e); // 7. 在链表头添加元素不用单独处理，调用add方法即可
}
// 在链表末尾添加新的元素e
public void addLast(E e) {
add(size, e);
}
}
① 代码1：现在的head节点，为虚拟头节点dummyHead
② 代码5：链表初始化的时候，虚拟头节点其存储的元素为null，指针next指向null
③ 代码6：由于我们在链表的头添加了一个虚拟头节点，所以当我们遍历的时候，需要多执行一次循环，才能找到prev节点
④ 代码7：由于添加了虚拟头节点，我们就不用额外的处理当索引为0的时候，而是可以复用add方法。
7. 链表的遍历、查询和修改
- 查询
// 查询
public E get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Add failed. Illegal index.");
}
Node cur = dummyHead.next;
for (int i = 0; i < index ; i++) {
cur = cur.next;
}
return cur.e;
}
① 首先对index索引进行校验，在校验之前我们要明白一件事情：在链表初始化的时候会创建一个虚拟头节点，而这个节点并不会导致size++，只有add了有意义的元素，才会导致size++。假设添加了a、b、c、d、e五个元素，size == 5，而最大索引index == 4，所以这里index不能等于size。
② 现在链表中的元素分别是a、b、c、d、e五个元素，当index == 4 的时候，我们只需要遍历4次，即从索引0开始遍历，到索引3即可，就能找到索引为index为4的位置的节点cur。如下图：
查询.jpg
- 查询第一个和最后一个元素：
// 查询第一个元素
public E getFirst(){
return get(0);
}
// 查询最后一个元素
public E getLast(){
return get(size - 1);
}
- 修改元素：
// 修改
public void set(int index, E e) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Add failed. Illegal index.");
}
Node cur = dummyHead.next;
for (int i = 0; i < index; i++)
cur = cur.next;
cur.e = e;
}
- 判断链表是否有元素e
// 判断链表中是否有元素e
public boolean contains(E e){
Node cur = dummyHead.next;
while (cur != null){
if(cur.e.equals(e))
return true;
cur = cur.next;
}
return false;
}
- 遍历：输出链表数据
@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();
}
8. 删除元素
删除索引2位置的元素
如果想要删除索引为2的位置的元素，我们只需要找到这个目标删除节点delNode的上一个节点prev，让prev的next指针指向原来delNode的next指针指向的节点，然后将delNode节点的next指针指向null即可
- 删除索引index位置的元素
// 删除元素
public E remove(int index){
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Remove failed. Illegal index.");
}
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;
}
- 删除链表第一个元素和最后一个元素
// 从链表中删除第一个元素，返回删除的元素
public E removeFirst(){
return remove(0);
}
// 从链表中删除最后一个元素，返回删除的元素
public E removeLast(){
return remove(size -1);
}
9. 测试
public class Test_Linkedlist {
public static void main(String[] args){
LinkedList<Integer> linkedList = new LinkedList<>();
for (int i = 0; i <5 ; i++) {
linkedList.addFirst(i);
System.out.println(linkedList.toString());
}
linkedList.set(2,666);
System.out.println(linkedList.toString());
Integer integer = linkedList.get(2);
System.out.println("索引2的位置的元素为："+integer);
linkedList.remove(2);
System.out.println(linkedList.toString());
linkedList.removeFirst();
System.out.println(linkedList.toString());
linkedList.removeLast();
System.out.println(linkedList.toString());
}
}
0->Null
1->0->Null
2->1->0->Null
3->2->1->0->Null
4->3->2->1->0->Null
4->3->666->1->0->Null
索引2的位置的元素为：666
4->3->1->0->Null
3->1->0->Null
3->1->Null
10. 时间复杂度分析
- 添加操作：O(n)
① addLast(e)---O(n)
② addFirst(e)---O(1)
③ add(index,e)---O(n) - 删除操作：O(n)
① removeLast---O(n)
② removeFirst---O(1)
③ remove(index,e)---O(n) - 查找操作：O(n)
① get(index)---O(n)
② contains(e)---O(n) -
修改操作：O(n)
① set(index,e)---O(n)
综上：增删改查都是O(n)，总体而言是比数组的性能要差的，所以它适合以下场景的操作：
链表应用场景
11. 后续
如果大家喜欢这篇文章，欢迎点赞！
如果想看更多 数据结构 方面的文章，欢迎关注!
