数据结构-LinkedList和链表
1.链表
1.1为什么要引入链表
上一篇文章中我们介绍了ArrayList，ArrayList的底层是通过数组实现的，具有随机访问效率高等特点，那么我们为什么还需要引入链表呢?
这是因为ArrayList底层通过数组实现，当在ArrayList任意位置(除了最后一位)进行插入和删除操作时，就需要将后续的元素整体向前或者向后进行搬移，时间复杂度为O(n)，效率比较低，由此可见ArrayList很不适合在一些插入或者删除操作较多的场景，而java集合中引入了链表，可以很好改善这个问题
1.2链表的概念和结构
链表是一种物理存储上非连续的存储结构，数据元素上的逻辑顺序是通过链表中的引用实现的。不同于数组，链表的物理存储单元可以分散在内存中的任意位置，通过节点(每个节点包含两部分：数据域和指针域。数据域用于存储数据元素，指针域则存储指向下一个节点的引用)之间的引用将它们连接起来形成一个线性序列
在Java中用对象引用代替指针
链表的结构多种多样，主要分为以下6种结构：
1.单向链表或双向链表
2.带头链表或者不带头链表
3.循环链表或者非循环链表
1.3实现一个单链表
public class SingleLinkedList{
//头插法
public void addFirst(int data){}
//尾插法
public void addLast(int data){}
//任意位置插入
public void addIndex(int index,int data){}
//查询链表中是否含有关键字key
public boolean contains(int key){}
//删除第一次出现关键字key的节点
public void remove(int key){}
//删除所有值为key的节点
public void removeAllKey(int data){}
//得到单链表的长度
public int size(){}
//清空所有节点，清空单链表
public void clear(){}
//打印单链表
public void display(){}
}实现思路：
1.addFirst(int data)在单链表头部进行插入操作，只需要创建一个新的节点将新节点的value属性赋值为data，并将新节点的next指向原来链表的头部节点即可
2.addLast(int data)在单链表尾部进行插入操作，只需要创建一个新的节点将新节点的value属性赋值为data，并将原链表尾部的节点的next指向新的节点即可
3.addIndex(int pos,int data)在链表指定位置插入元素，首先要判断插入的位置是否合法，如果合法则分别需要修改要将原来插入位置的元素的next指向新节点，并且新节点的next要指向插入位置后面的那个节点
4.contains(int key)判断链表是否包含元素key，只需要依次遍历链表，获取到每个节点的元素并进行判断
5.remove(int key)删除元素key，遍历链表，找到key所在的位置，将key前一个元素的next指向key后面的元素即可
6.removeAllKey(int key)删除元素值为key的所有元素，每找到一个值为key的元素要进行判断key是否有前后节点，再进行相应的删除操作
7.size()返回链表中的节点个数，可以通过遍历链表并设置计数器，通过计数器统计链表中结点的个数
8.display()打印链表，遍历并依次打印每个节点的元素
2.LinkedList
2.1什么是LinkedList
LinkedList是Java集合框架中的链表，LinkedList是基于双向链表实现的，由于链表中没有将元素存储在连续的空间内，元素存储在单独的节点中，然后通过引用将节点连接起来，因此在任意位置插入或者删除元素，不需要搬移元素，效率比较高。
LinkedList中的节点结构：
说明：
1.LinkedList实现了List接口
2.LinkedList的底层使用了双向链表
3.LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问
4.LinkedList的任意位置插入和删除操作效率比较高，时间复杂度为O(1)
5.LinkedList比较适合插入删除比较多的场景
6.LinkedList的访问效率比较低，时间复杂度为O(n)
2.2LinkedList的构造方法
| 方法 | 解释 |
| LinkedList() | 无参构造 |
| public LinkedList(Collection<? extends E> c) | 使用其他集合容器种的元素构造List |
代码演示：
public class Test {
public static void main(String[] args) {
//构造一个空的LinkedList
List<Integer> list1=new LinkedList<>();
System.out.println(list1);
List<String> list=new java.util.ArrayList<>();
list.add("hajimi");
list.add("hahaha");
list.add("lalala");
//使用ArrayList构造LinkedList
List<String> list2=new LinkedList<>(list);
System.out.println(list2);
}
}
2.3LinkedList的常用方法
| 方法 | 解释 |
| boolean add(E,e) | 在尾部插入元素e |
| void add(int index,E e) | 将元素e插入到index的位置 |
| boolean addAll(Collection<? extends E> c) | 在尾部插入c中的所有元素 |
| E remove(int index) | 删除index位置的元素 |
| boolean remove(Object o) | 删除第一个o元素 |
| E get(int index) | 获取下标为index位置元素 |
| E set(int index,E e) | 将下标为index位置的元素设置为e |
| void clear() | 清空链表中的所有元素 |
| boolean contains(Object o) | 判断o是否在线性表中 |
| int indexOf(Object o) | 返回第一个o所在的下标 |
| int lastIndexOf(Object o) | 返回最后一个o所在的下标 |
| List<E> subList(int fromIndex,int toIndex) | 截取部分list |
代码演示：
import java.util.*;
public class Test {
public static void main(String[] args) {
List<String> list=new LinkedList<>();
//在链表末尾插入元素
list.add("My");
list.add("name");
list.add("hajimi");
System.out.println(list);
//在指定位置插入元素
list.add(2,"is");
System.out.println(list);
list.add(4,"king");
System.out.println(list);
//删除指定位置的元素
list.remove(4);
System.out.println("进行删除操作后的链表"+list);
//删除指定元素
list.remove("My");
System.out.println("进行删除操作后的链表"+list);
//获取指定位置的元素
System.out.println(list.get(2));
//将指定位置下标的元素设置为e
System.out.println(list.set(0,"Your name"));
System.out.println(list);
//判断线性表中是否包含某元素
System.out.println(list.contains("hajimi"));
list.add("hajimi");
//返回指定元素第一个出现的下标
System.out.println(list.indexOf("hajimi"));
//返回指定元素最后一次出现的下标
System.out.println(list.lastIndexOf("hajimi"));
//截取部分链表内容
List<String> partList;
partList=list.subList(0,3);
System.out.println("截取的部分："+partList);
//在链表尾部插入其他容器的所有元素
list.addAll(partList);
System.out.println(list);
//清空链表中的所有元素
list.clear();
System.out.println(list);
}
}
2.4LinkedList的遍历
LinkedList遍历主要有3中方式：
1.使用for循环搭配链表长度进行遍历
2.使用foreach循环
3.使用迭代器进行遍历
代码演示：
import java.util.*;
public class Test {
public static void main(String[] args) {
List<String> list=new LinkedList<>();
list.add("My");
list.add("name");
list.add("is");
list.add("hajimi");
list.add("king");
list.add("!");
//使用for循环搭配链表长度进行遍历链表
for (int i=0;i<list.size();i++){
System.out.print(list.get(i)+" ");
}
System.out.println();
//使用foreach循环遍历链表
for(String s:list){
System.out.print(s+" ");
}
System.out.println();
//使用迭代器遍历链表
//正向遍历
ListIterator<String> it= list.listIterator();
while(it.hasNext()){
System.out.print(it.next()+" ");
}
System.out.println();
//反向遍历
ListIterator<String> rit= list.listIterator(list.size());
while (rit.hasPrevious()){
System.out.print(rit.previous()+" ");
}
}
}2.5实现一个LinkedList
LinkedList原码中节点的结构如下：
实现一个泛型为Integer的链表，代码演示：
public class MyLinkedList2 {
static class ListNode{
private ListNode prev;
private int val;
private ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;
public ListNode tail;
public MyLinkedList2(){
}
//头插法
public void addFirst(int data){
ListNode newNode=new ListNode(data);
if(head==null){
head=tail=newNode;
}else {
newNode.next=head;
head.prev=newNode;
head=newNode;
}
}
//尾插法
public void addLast(int data){
ListNode newNode=new ListNode(data);
if(head==null){
head=tail=newNode;
}else {
newNode.prev=tail;
tail.next=newNode;
tail=newNode;
}
}
//任意位置插入,第一个数据节点为0号下标
public boolean addIndex(int index,int data){
if(index<0||index>size()){
System.out.println("要插入的位置不合法");
return false;
}
if(index==0){
addFirst(data);
return true;
}
if(index==size()){
addLast(data);
return true;
}
ListNode cur=head;
while(index!=0){
cur=cur.next;
index--;
}
ListNode newNode=new ListNode(data);
newNode.next=cur;
newNode.prev=cur.prev;
cur.prev.next=newNode;
cur.prev=newNode;
return true;
}
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key){
if (head==null){
System.out.println("链表为空");
return false;
}
ListNode cur=head;
while (cur!=null){
if(cur.val==key){
System.out.println("找到了!");
return true;
}
cur=cur.next;
}
System.out.println("没找到");
return false;
}
//删除第一次出现关键字为key的节点
public void remove(int key){
if (head==null){
System.out.println("链表中没有元素，无法进行删除");
return;
}
ListNode cur=head;
while (cur!=null){
if(cur.val==key){
//判断是否是链表尾部删除
if(cur.next==null){
cur.prev.next=null;
tail=tail.prev;
}
//删除中间节点操作
cur.prev.next=cur.next;
cur.next.prev=cur.prev;
}
cur=cur.next;
}
//判断首节点情况
if(head.val==key){
//如果链表只有一个节点，需要进行特殊处理
if(head.next!=null){
head=head.next;
head.prev=null;
}else {
head=null;
}
}
}
//删除所有值为key的节点
public void removeAllKey(int key){
if(head==null){
return;
}
ListNode cur=head.next;
while(cur!=null){
if(cur.val==key){
if(cur.next==null){
cur.prev.next=null;
tail=tail.prev;
}else{
cur.prev.next=cur.next;
cur.next.prev=cur.prev;
}
}
cur=cur.next;
}
if(head.val==key){
if(head.next==null){
head=null;
}else{
head=head.next;
head.prev=null;
}
}
}
//得到单链表的长度
public int size(){
int count=0;
ListNode cur=head;
while(cur!=null){
cur=cur.next;
count++;
}
return count;
}
public void display(){
ListNode cur=head;
if(head==null){
return;
}
while(cur!=null){
System.out.print(cur.val+" ");
cur=cur.next;
}
System.out.println();
}
public void clear(){
ListNode cur=head;
if(head==null){
return;
}
while(cur!=null){
ListNode curNext=cur.next;
cur.prev=null;
cur.next=null;
cur=curNext;
}
//处理还在引用的head和tail
head=null;
tail=null;
}
}
对上述代码进行运行测试：
public class Test {
public static void main(String[] args) {
MyLinkedList2 myLinkedList2=new MyLinkedList2();
myLinkedList2.addLast(1);
myLinkedList2.addLast(2);
myLinkedList2.addFirst(3);
myLinkedList2.addIndex(2,6);
myLinkedList2.addIndex(0,5);
myLinkedList2.addIndex(1,4);
myLinkedList2.display();
System.out.println(myLinkedList2.contains(6));
myLinkedList2.remove(6);
myLinkedList2.display();
myLinkedList2.addFirst(1);
myLinkedList2.display();
myLinkedList2.removeAllKey(1);
myLinkedList2.display();
System.out.println(myLinkedList2.size());
myLinkedList2.clear();
myLinkedList2.display();
}
}
3.LinkedList的特点
LinkedList的特点主要体现在以下几个方面：
1.数据存储的方式
LinkedList是通过一系列节点组成的，每个节点都包含三个部分，数据元素，指向前一个节点的引用和指向后一个节点的引用，链表的内存是动态分配的，每个节点的内存空间是独立分配的，使得链表的大小灵活可调
2.操作效率
在链表头部或者尾部插入和删除元素操作的时间复杂度为O(1)，如果已经获得目标节点的引用，进行插入和删除操作的时间复杂度为O(1)，但如果没有则需要从头遍历找到目标位置，时间复杂度为O(n)
链表不支持随机访问，方位任意元素都需要从头开始进行遍历，时间复杂度为O(n)
3.内存使用
每个节点除了存取数据元素外，还需要存储引用，有额外的内存开销。链表的内存分配时动态的，不会像数组那样分配固定的大小
4.适用场景
适合插入和删除频繁的场景，不适合随机访问的场景，适合数据量不确定的场景(动态扩展，不过多浪费空间)
4.LinkedList和ArrayList的区别
| 不同点 | ArrayList | LinkedList |
| 存储空间上 | 物理上连续的 | 逻辑上连续，物理上不一定连续 |
| 随机访问 | 支持，时间复杂度O(1) | 不支持，时间复杂度O(n) |
| 插入/删除 | 需要搬运元素，效率低，时间复杂度O(n) | 只需要修改引用的指向，时间复杂度O(1) |
| 扩容机制 | 当数组空间不足时，会创建一个更大的数组并复制原数据 | 动态分配内存，每次插入时动态分配新节点 |
| 内存使用 | 内存分配连续，可能有空间浪费（预留空间），但内存使用效率较高。 | 每个节点需要额外存储指针，内存使用相对较高。 |
| 适用场景 | 元素频繁访问的场景 | 插入删除频繁的场景 |
原文地址：https://blog.csdn.net/2301_76928097/article/details/145236560
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！