前言
本篇博客给大家带来的是链表的知识点, 其中包括面试经常会提问的真题 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);}
}
第二种构造方法与 顺序表中第二种构造方法相似. 这里看不懂的可以去上篇看看顺序表中关于构造方法的讲解.
2.LinekedList的其他常用方法
int indexOf(Object o) 返回第一个o所在下标
int lastlndexOf(Object 0) 返回最后一个o的下标
List<E> subList(int fromlndex, int tolndex) 截取部分 list
5.ArrayList和LinkedList的区别
从不同点处记忆即可