数据结构-3.链表

前言

本篇博客给大家带来的是链表的知识点, 其中包括面试经常会提问的真题 ArrayList 和 LinkedList 的区别 .

文章专栏: Java-数据结构

若有问题评论区见

欢迎大家点赞评论收藏分享

如果你不知道分享给谁,那就分享给薯条, 如果分享不成功, 那我就会回你一下,那样你就分享成功啦.

你们的支持是我不断创作的动力 .

1.ArrayList的存在的问题

1.ArrayList底层使用连续的空间, 任意位置插入或者删除元素时, 需要将该位置后面的元素整体往前或往后移动,故时间复杂度为 O(N) .

2.增容需要申请新的空间, 拷贝数据, 释放旧空间会有不小的消耗 .

3.增容一般是呈1.5倍或2倍增长,势必会有一定的空间浪费. 例如当前容量为100时, 假设呈二倍增长,满了以后增容到200, 我们再继续插入5个数据, 后面没有数据插入的话就浪费了95个数据空间.

如果我们想要达到那种随用随取, 有几个数据我就增几个空间,那我们该怎么办呢? - 就是今天要介绍的链表了

2.链表

2.1链表的概念及结构

链表是一种物理存储结构上非连续存储结构, 数据元素的逻辑顺序是通过链表种的引用链接次序实现的.

注意:

1. 从上图可看出, 链式结构再逻辑上是连续的的,但是在物理上不一定连续.

2. 现实中的结点一般都是从堆上申请出来的

3. 从堆上申请的空间, 是按照一定的策略来分配的, 两次申请的空间可能连续, 也可能不连续

实际中链表的结构非常多样, 一下情况组合起来就有8种链表结构 :

1. 单向或者双向

2.带头或者不带头

3.循环或者非循环

虽然有8种链表的结构, 但是我们重点掌握两种:

1.无头单向非循环链表: 结构简单, 一般不会单独用来存数据. 实际种更多的是作为其他数据结构的子结构, 如: 哈希桶, 图的邻接表等等. 另外这种结构在笔试面试中出现很多.

2.无头双向链表: 在Java的集合框架库中LinkedList 底层实现就是无头双向循环链表.

2.2链表的实现(无头单向非循环链表)

写到这里, 我想起上篇顺序表的实现 , 我直接把代码一丢没做任何解释, 会让初学者看得很难受, 所以这次我得改正这个错误, 尽量让大家都能看懂并且会自己写. 其实解释也是很耗费时间的, 作为一名大二的学生😭, 上专业课和看网课就让我的时间所剩无几, 完后还要写blog, 我真是累成狗了🐶. 但是我还是很开心的, 一方面能够给大家带来知识, 另一方面也是在巩固我的知识.

第一步创建一个类 MySingleList

我们都知道节点是链表里面的 , 所以节点就是链表的成员,这没有问题,

那问题来了, 节点中的数据data呢? 它可以定义为链表的成员吗?

显然是不行的, 因为data是节点里面的, 只需要,在MySingleList类当中再定义一个内部类ListNode就可以解决了.

public class MySingleList {//因为节点是链表的一部分,所以可以将其定义为内部类static class ListNode {public int val;//节点的值域public ListNode next;//下一个节点的地址public ListNode(int val) {this.val = val;}}
public ListNode head;//表示当前链表的头节点
}

所以有了上述代码. 那么接着我想要实现链表的头插法, 尾插法. 我发现没有链表,

那么就自己手动实现一个简单点的,

// 头插法

public void addFirst ( int data ){

}

// 尾插法

public void addLast ( int data ){

}

public class MySingleList {//因为节点是链表的一部分,所以可以将其定义为内部类static class ListNode {public int val;//节点的值域public ListNode next;//下一个节点的地址public ListNode(int val) {this.val = val;}}public ListNode head;//表示当前链表的头节点//手动实现简单链表
public  void createList() {ListNode node1 = new ListNode(12);ListNode node2 = new ListNode(23);ListNode node3 = new ListNode(34);ListNode node4 = new ListNode(45);ListNode node5 = new ListNode(56);node1.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;this.head = node1;}
}

好, 到这里我们就可以来实现链表的基本操作:

第二步实现链表的基本操作

遍历单链表:

//遍历单链表public void display() {//指向头节点的引用不能动,所以利用cur代替ListNode cur = this.head;while(cur != null) {System.out.print(cur.val+" ");cur = cur.next;}System.out.println();}

求链表的长度:

//得到单链表的长度public int size(){int count = 0;ListNode cur = this.head;while(cur != null) {count++;cur = cur.next;}return count;}

查找关键字key是否包含在链表中:

//查找关键字key是否包含在单链表当中public boolean contains(int key) {ListNode cur = this.head;while (cur != null) {if(key == cur.val) {return true;}cur = cur.next;}return false;}

头插法:

//头插法public void addFirst(int data) {ListNode node = new ListNode(data);node.next = head;head = node;}

尾插法:

public void addLast(int data) {ListNode node = new ListNode(data);ListNode  cur = this.head;if(cur == null) {head = node;return;}while(cur.next != null) {cur = cur.next;}cur.next = node;node.next = null;}

任意位置插入,第一个数据节点为0号下标:

//任意位置插入,第一个数据节点为0号下标public void addIndex(int index, int data) {if(index < 0 || index > size()) {System.out.println("index 不合法");return;}if(index == 0) {addFirst(data);return;}if(index == size()) {addLast(data);return;}int count = 0;ListNode node = new ListNode(data);ListNode cur = this.head;while(count != index-1) {cur = cur.next;count++;}node.next = cur.next;cur.next = node;}

清除链表, 直接把head赋值为空即可:

//清除单链表public void clear() {this.head = null;}

删除第一个值为key的节点:

//删除第一个关键字为key的节点public void remove(int key){if(head == null) {return;}//单独删除头节点if(head.val == key) {head = head.next;return;}ListNode cur = searchPrev(key);if(cur == null) {System.out.println("没有找到key");return;}ListNode del = cur.next;cur.next = del.next;}//找到关键字key的前驱private ListNode searchPrev(int key) {ListNode cur = this.head;while(cur.next != null) {if(cur.next.val == key) {return cur;}cur = cur.next;}return null;}

删除值为key的所有节点:

 //删除所有关键为key的节点public void removeAll(int key){if(head == null) {return;}ListNode prev = this.head;ListNode cur = this.head.next;while(cur != null) {if(cur.val == key) {prev.next = cur.next;cur = cur.next;}else {prev = cur;cur = cur.next;}}if(head.val == key) {head = head.next;}}

下面是全部代码:

//因为节点是链表的一部分,所以可以将其定义为内部类static class ListNode {public int val;//节点的值域public ListNode next;//下一个节点的地址public ListNode(int val) {this.val = val;}}public ListNode head;//表示当前链表的头节点public  void createList() {ListNode node1 = new ListNode(12);ListNode node2 = new ListNode(23);ListNode node3 = new ListNode(34);ListNode node4 = new ListNode(45);ListNode node5 = new ListNode(56);node1.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;this.head = node1;}//遍历单链表public void display() {//指向头节点的引用不能动,所以利用cur代替ListNode cur = this.head;while(cur != null) {System.out.print(cur.val+" ");cur = cur.next;}System.out.println();}//得到单链表的长度public int size(){int count = 0;ListNode cur = this.head;while(cur != null) {count++;cur = cur.next;}return count;}//查找关键字key是否包含在单链表当中public boolean contains(int key) {ListNode cur = this.head;while (cur != null) {if(key == cur.val) {return true;}cur = cur.next;}return false;}//头插法public void addFirst(int data) {ListNode node = new ListNode(data);node.next = head;head = node;}//尾插法public void addLast(int data) {ListNode node = new ListNode(data);ListNode  cur = this.head;if(cur == null) {head = node;return;}while(cur.next != null) {cur = cur.next;}cur.next = node;node.next = null;}//任意位置插入,第一个数据节点为0号下标public void addIndex(int index, int data) {if(index < 0 || index > size()) {System.out.println("index 不合法");return;}if(index == 0) {addFirst(data);return;}if(index == size()) {addLast(data);return;}int count = 0;ListNode node = new ListNode(data);ListNode cur = this.head;while(count != index-1) {cur = cur.next;count++;}node.next = cur.next;cur.next = node;}//删除第一个关键字为key的节点public void remove(int key){if(head == null) {return;}//单独删除头节点if(head.val == key) {head = head.next;return;}ListNode cur = searchPrev(key);if(cur == null) {System.out.println("没有找到key");return;}ListNode del = cur.next;cur.next = del.next;}//找到关键字key的前驱private ListNode searchPrev(int key) {ListNode cur = this.head;while(cur.next != null) {if(cur.next.val == key) {return cur;}cur = cur.next;}return null;}//删除所有关键为key的节点public void removeAll(int key){if(head == null) {return;}ListNode prev = this.head;ListNode cur = this.head.next;while(cur != null) {if(cur.val == key) {prev.next = cur.next;cur = cur.next;}else {prev = cur;cur = cur.next;}}if(head.val == key) {head = head.next;}}//清除单链表public void clear() {this.head = null;}

3.LinkedList的模拟实现(无头双向链表)

无头双向链表跟上述的单向链表的实现大致相同,不过是多了一个前驱,故不做解释

static class ListNode {private int val;//数据域private ListNode prev;//前驱private ListNode next;//后继public ListNode(int val) {this.val = val;}}public ListNode head;//双向链表的头节点.public ListNode last;//双向链表的尾节点.//头插法public void addFirst(int data){ListNode node = new ListNode(data);if(head == null) {head = node;last = node;}else{head.prev = node;node.next = head;head = node;}}//尾插法public void addLast(int data){ListNode node = new ListNode(data);if(head == null) {last = node;head = node;}else {last.next = node;node.prev = last;last = node;}}//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data){ListNode node = new ListNode(data);ListNode cur = head;if(index == 0) {addFirst(data);return;}if(index == size()) {addLast(data);return;}if(index != 0 && index != size()) {for (int i = 0; i < index-1; i++) {cur = cur.next;}node.next = cur.next;cur.next.prev = node;cur.next = node;node.prev = cur;}}
//判断Index是否合法private void checkIndex(int index) {if(index < 0 || index > size()) {throw new IndexOutOfException("index 不合法" + index);}}//查找是否包含关键字key是否在链表当中public boolean contains(int key){ListNode cur = head;while(cur != null) {if(cur.val == key) {return true;}cur = cur.next;}return false;}//删除第一次出现关键字为key的节点public void remove(int key){ListNode cur = head;if(head.val == key) {head = head.next;if(head != null) {//考虑只有一个节点的情况下head.prev = null;}else{last = null;}return;}if(last.val == key) {last = last.prev;last.next = null;return;}while(cur != null) {if(cur.val == key) {cur.prev.next = cur.next;cur.next.prev = cur.prev;return;}cur = cur.next;}}//删除所有值为key的节点public void removeAllKey(int key){ListNode cur = head;while(cur != null) {if(cur.val == key) {if(cur == head) {head = head.next;head.prev = null;cur = cur.next;continue;}if(cur == last) {last = last.prev;last.next = null;cur = cur.next;continue;}cur.prev.next = cur.next;cur.next.prev = cur.prev;cur = cur.next;}cur = cur.next;}}//得到链表的长度public int size(){ListNode cur = head;int count = 0;while(cur != null) {cur = cur.next;count++;}return count;}//遍历链表public void display(){ListNode cur = head;for (int i = 0; i < size(); i++) {System.out.print(cur.val + " ");cur = cur.next;}System.out.println();}//清除链表public void clear(){/*ListNode cur = head;while(cur.next != null) {cur = cur.next;cur.prev.next = null;cur.prev = null;}//while循环走出来有两种情况://1.head.next = null;//2.cur走到了尾节点.if(head.next == null) {head = head.next;}else {cur.prev = null;}head = null;last = null;*///gaobo写法:ListNode cur = head;while(cur != null) {ListNode curNext = cur.next;cur.prev = null;cur.next = null;cur = curNext;}head = null;last = null;}

4.LinkedList的使用

4.1LinkedList的介绍

LinkedList的官方文档:

LinkedList (Java Platform SE 8 ) (oracle.com)

由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。

说明:

1. LinkedList实现了List接口

2. LinkedList的底层使用了双向链表

3. LinkedList没有实现RandomAccess接口, 因此LinkedList不支持随机访问

4. LinkedList的任意位置插入和删除元素时的效率比较高,时间复杂度为O(1)

5. LinkedList比较适合任意位置插入的场景

4.2LinkedList的使用

1.LinkedList的构造

public class Test3 {public static void main(String[] args) {//构造一个空的LinkedListList<Integer> list1 = new LinkedList<>();List<String> list2 = new ArrayList<>();list2.add("2334");list2.add("ieie");list2.add("uuy");//使用ArrayList构造LinkedListList<String> list3 = new LinkedList<>(list2);System.out.println(list3);}
}