java的LinkedList

news/2024/10/15 8:29:32/

java的LinkedList

  • 什么是LinkedList
  • LinkedList的模拟实现
  • LinkedList的使用
  • ArrayList和LinkedList的区别

什么是LinkedList

LinkedList的官方文档
LinkedList的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的结点中，然后通过引用将结点连接起来了，因此在任意位置插入或删除元素时，不需要搬移元素，效率比较高。
在这里插入图片描述
说明：

  1. LinkedList实现了List接口
  2. LinkedList的底层使用了双向链表
  3. LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问
  4. LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)
  5. LinkedList比较适合任意位置插入的场景

LinkedList的模拟实现

在这里插入图片描述

java">public interface IList {//头插法public void addFirst(int data);//尾插法public void addLast(int data);//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data);//查找是否包含关键字key是否在双向链表当中public boolean contains(int key);//删除第一次出现关键字为key的节点public void remove(int key);//删除所有值为key的节点public void removeAllKey(int key);//得到双向链表的长度public int size();public void clear();public void display();
}

java">public class MyLinkedList implements IList{static class ListNode{public int val;public ListNode prev;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;public ListNode last;@Overridepublic void addFirst(int data) {}@Overridepublic void addLast(int data) {}@Overridepublic void addIndex(int index, int data) {}@Overridepublic boolean contains(int key) {return false;}@Overridepublic void remove(int key) {}@Overridepublic void removeAllKey(int key) {}@Overridepublic int size() {return 0;}@Overridepublic void clear() {}@Overridepublic void display() {}}

我们先来实现打印链表和得到链表长度

java">@Override
public int size() {ListNode cur = this.head;int count = 0;while(cur != null){cur = cur.next;count++;}return count;
}
@Override
public void display() {ListNode cur = this.head;while(cur != null){System.out.print(cur.val + " ");cur = cur.next;}System.out.println();
}

接下来实现头插法

在这里插入图片描述

java">@Override
public void addFirst(int data) {ListNode newNode = new ListNode(data);if(this.head == null){head = last = newNode;return;}head.prev = newNode;newNode.next = head;head = newNode;
}

java">public class Test {public static void main(String[] args) {MyLinkedList list = new MyLinkedList();list.addFirst(56);list.addFirst(45);list.addFirst(34);list.addFirst(23);list.addFirst(12);list.display();list.addFirst(33);list.display();System.out.println(list.size());}//结果为：//12 23 34 45 56 //33 12 23 34 45 56 //6
}

实现尾插法
在这里插入图片描述

java">@Override
public void addLast(int data) {ListNode newNode = new ListNode(data);if(head == null){head = last = newNode;return;}last.next = newNode;newNode.prev = last;;last = newNode;
}

java">public class Test {public static void main(String[] args) {MyLinkedList list = new MyLinkedList();list.addLast(12);list.addLast(23);list.addLast(34);list.addLast(45);list.addLast(56);list.display();}//结果为：//12 23 34 45 56
}

实现任意位置插入,第一个数据节点为0号下标
在这里插入图片描述

java">private ListNode findIndex(int index){ListNode cur = this.head;while(index != 0){cur = cur.next;index--;}return cur;
}
@Override
public void addIndex(int index, int data) {int len = size();if(index < 0 || index > len - 1){return;}if(index == 0){addFirst(data);return;}if(index == len - 1){addLast(data);return;}ListNode cur = findIndex(index);ListNode newNode = new ListNode(data);newNode.next = cur;cur.prev.next = newNode;newNode.prev = cur.prev;cur.prev = newNode;
}

java">public class Test {public static void main(String[] args) {MyLinkedList list = new MyLinkedList();list.addLast(12);list.addLast(23);list.addLast(34);list.addLast(45);list.addLast(56);list.display();list.addIndex(2,33);list.display();list.addIndex(0,33);list.display();list.addIndex(6,33);list.display();list.addIndex(8,33);list.display();}//结果为：//12 23 34 45 56//12 23 33 34 45 56//33 12 23 33 34 45 56//33 12 23 33 34 45 56 33//33 12 23 33 34 45 56 33
}

实现删除第一次出现关键字为key的节点
在这里插入图片描述

java">@Override
public void remove(int key) {ListNode cur = this.head;while(cur != null){if(cur.val == key){if(cur == this.head){head = head.next;if(head != null){head.prev = null;}}else{cur.prev.next = cur.next;if(cur.next == null){last = last.prev;}else{cur.next.prev = cur.prev;}}return;}cur = cur.next;}
}

java">public class Test {public static void main(String[] args) {MyLinkedList list = new MyLinkedList();list.addLast(12);list.addLast(23);list.addLast(34);list.addLast(45);list.addLast(56);list.display();list.remove(12);list.display();list.remove(56);list.display();list.remove(34);list.display();}//结果为：//12 23 34 45 56//23 34 45 56//23 34 45//23 45
}

删除所有值为key的节点，我们只需要在删除第一次出现关键字为key的节点的代码上将return删除掉，让其循环到链表结尾

java">@Override
public void removeAllKey(int key) {ListNode cur = this.head;while(cur != null){if(cur.val == key){if(cur == this.head){head = head.next;if(head != null){head.prev = null;}}else{cur.prev.next = cur.next;if(cur.next == null){last = last.prev;}else{cur.next.prev = cur.prev;}}}cur = cur.next;}
}

java">public class Test {public static void main(String[] args) {MyLinkedList list = new MyLinkedList();list.addLast(23);list.addLast(33);list.addLast(34);list.addLast(23);list.addLast(23);list.display();list.removeAllKey(23);list.display();}//结果为：//23 33 34 23 23//33 34
}

实现查找是否包含关键字key是否在双向链表当中，我们只需要遍历链表，找到返回true，没找到返回false

java">@Override
public boolean contains(int key) {ListNode cur = this.head;while(cur != null){if(cur.val == key){return true;}cur = cur.next;}return false;
}

java">public class Test {public static void main(String[] args) {MyLinkedList list = new MyLinkedList();list.addLast(12);list.addLast(23);list.addLast(34);list.addLast(45);list.addLast(56);list.display();System.out.println(list.contains(34));System.out.println(list.contains(100));}//结果为：//12 23 34 45 56//true//false
}

接下来实现clear，我们可以直接暴力的将head和last置为null
但是最后是将每个结点的prev和last都置为null，我们需要一个curN保留下一个结点，最后还需要将head和last置为null

java">@Override
public void clear() {ListNode cur = this.head;while(cur != null){ListNode curN = cur.next;cur.prev = null;cur.next = null;cur = curN;}this.head = this.last = null;
}

java">public class Test {public static void main(String[] args) {MyLinkedList list = new MyLinkedList();list.addLast(12);list.addLast(23);list.addLast(34);list.addLast(45);list.addLast(56);list.display();list.clear();list.display();}//结果为：//12 23 34 45 56//
}

LinkedList的使用

  1. LinkedList的构造
方法解释
LinkedList ()无参构造
LinkedList (Collection<? extends E> c)利用其他集合容器中元素构造List
java">import java.util.ArrayList;
import java.util.LinkedList;
public class Test {public static void main(String[] args) {//构造一个空的LinkedListLinkedList<Integer> list1 = new LinkedList<>();list1.add(1);list1.add(2);list1.add(3);list1.add(4);list1.add(5);System.out.println(list1);ArrayList<Integer> list2 = new ArrayList<>();list2.add(11);list2.add(22);list2.add(33);list2.add(44);list2.add(55);//使用ArrayList构造LinkedListLinkedList<Integer> list3 = new LinkedList<>(list2);System.out.println(list3);}//结果为：//[1, 2, 3, 4, 5]//[11, 22, 33, 44, 55]
}
  1. LinkedList的其他常用方法介绍
方法解释
boolean add(E e)尾插 e
void add(int index, E element)将 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 element)将下标 index 位置元素设置为 element
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
java">import java.util.LinkedList;
import java.util.List;
public class Test {public static void main(String[] args) {LinkedList<Integer> list1 = new LinkedList<>();list1.add(1);   //add(elem)表示尾插list1.add(2);list1.add(3);list1.add(4);list1.add(5);System.out.println(list1.size());   //5System.out.println(list1);      //[1, 2, 3, 4, 5]//在起始位置插入0list1.add(0,0);    //add(index,elem);在index位置插入元素elemSystem.out.println(list1);      //[0, 1, 2, 3, 4, 5]list1.remove();     //remove();删除第一个元素，内部调用的是removeFirst()System.out.println(list1);  //[1, 2, 3, 4, 5]list1.removeFirst();    //removeFirst();删除第一个元素System.out.println(list1);  //[2, 3, 4, 5]list1.removeLast();     //removeLast();删除最后一个元素System.out.println(list1);  //[2, 3, 4]list1.remove(1);    //remove(index);删除index位置的元素System.out.println(list1);  //[2, 4]//contains(elem):检测elem元素是否存在，如果存在返回true，否则返回falseif(!list1.contains(1)){list1.add(0,1);}System.out.println(list1);  //[1, 2, 4]list1.addLast(1);System.out.println(list1);  //[1, 2, 4, 1]System.out.println(list1.indexOf(1));   //indexOf(elem);从前往后找第一个elem的位置 0System.out.println(list1.lastIndexOf(1));   //lastIndexOf(elem);从后往前找第一个elem的位置 3int elem = list1.get(0);    //get(index);获取指定位置元素System.out.println(elem);   // 1list1.set(0,100);   //set(index,elem);将index位置的元素设置为elemSystem.out.println(list1);  //[100, 2, 4, 1]//subList(from,to):用list1中[from,to)之间的元素构造一个新的LinkedList返回List<Integer> copy = list1.subList(0,3);System.out.println(list1);  //[100, 2, 4, 1]System.out.println(copy);   //[100, 2, 4]list1.clear();  //将list1中元素清空System.out.println(list1.size());   //0}
}
  1. LinkedList的遍历
java">public class Test {public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);System.out.println(list);System.out.println("======for=====");for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i) + " ");}System.out.println();System.out.println("======for each=====");for(int x : list){System.out.print(x + " ");}System.out.println();System.out.println("======Iterator=====");Iterator<Integer> it = list.iterator();while(it.hasNext()){System.out.print(it.next() + " ");}System.out.println();System.out.println("======ListIterator=====");ListIterator<Integer> lit = list.listIterator();while(lit.hasNext()){System.out.print(lit.next() + " ");}System.out.println();System.out.println("======ListIterator拓展=====");ListIterator<Integer> lit2 = list.listIterator(list.size());while(lit.hasPrevious()){System.out.print(lit.previous() + " ");}}//结果为：//[1, 2, 3, 4, 5]//======for=====//1 2 3 4 5//======for each=====//1 2 3 4 5//======Iterator=====//1 2 3 4 5 //======ListIterator=====//1 2 3 4 5//======ListIterator拓展=====//5 4 3 2 1
}

ArrayList和LinkedList的区别

不同点ArrayListLinkedList
存储空间上物理上一定连续逻辑上连续，但物理上不一定连续
随机访问支持：O(1)不支持：O(N)
头插需要搬移元素，效率低O(N)只需修改引用的指向，时间复杂度为O(1)
插入空间不够时需要扩容没有容量的概念
应用场景元素高效存储+频繁访问任意位置插入和删除元素频繁

本篇文章到此，谢谢阅读，希望对您有帮助。


http://www.ppmy.cn/news/1539353.html

相关文章

迈巴赫S480升级原厂魔毯悬挂功能有哪些作用

迈巴赫S480升级原厂魔毯悬挂功能有哪些作用

迈巴赫 S480 升级魔毯空气悬挂系统的功能介绍如下&#xff1a; 1. 平稳驾驶体验&#xff1a; • 路况适应&#xff1a;通过摄像头和雷达扫描车前方路面状况&#xff0c;提前获取路况信息&#xff0c;然后根据这些信息自动调节空气悬挂的软硬程度。无论是在平坦的高速公路&…
阅读更多...
Linux内核 -- 读写同步机制之序列锁 read_seqbegin 作用与用法

Linux内核 -- 读写同步机制之序列锁 read_seqbegin 作用与用法

read_seqbegin 函数的作用与用法 read_seqbegin 是 Linux 内核中的一个函数&#xff0c;用于在内核实现轻量级的读写同步机制时读取序列锁&#xff08;sequence lock&#xff09;的状态。序列锁是一种适合读多写少的场景的锁机制&#xff0c;允许多个读取者并发读取&#xff0…
阅读更多...
kafka脚本工具使用

kafka脚本工具使用

如何定位kakfa消费端消息异常问题 查看主题查看消费者组查看消费者详情&#xff08;LAG: 消费者与最新消息的滞后程度(数字越大说明消费者处理消息的速度越慢)&#xff09; 进入docker容器&#xff0c;直接运行sh脚本即可 docker exec -it <containerName> /bin/bash或…
阅读更多...
使用Uniapp开发微信小程序实现一个自定义的首页顶部轮播图效果？

使用Uniapp开发微信小程序实现一个自定义的首页顶部轮播图效果？

在Uniapp中开发微信小程序&#xff0c;并实现自定义首页顶部轮播图的效果&#xff0c;可以通过使用Uniapp的组件如swiper和swiper-item来完成。这是一个常见的需求&#xff0c;下面是一个完整的示例代码&#xff0c;展示如何实现一个简单的自定义轮播图效果。 创建页面结构 首…
阅读更多...
牛客.字符串替换​编辑神奇数牛客DNA序列牛客.kotori和气球

牛客.字符串替换​编辑神奇数牛客DNA序列牛客.kotori和气球

目录 牛客.字符串替换​编辑 神奇数 牛客DNA序列 牛客.kotori和气球 牛客.字符串替换 import java.util.*;public class StringFormat {public String formatString(String A, int n, char[] arg, int m) { //这里是使用了StringBuffer来去接受这个StringBuffer retnew Stri…
阅读更多...
go+bootstrap实现简单的注册登录和管理

go+bootstrap实现简单的注册登录和管理

概述 使用&#xff0c;gomysql实现了用户的登录&#xff0c;注册&#xff0c;和管理的简单功能&#xff0c;不同用户根据不同权限显示不同的内容 实战要求&#xff1a; 1、用户可以注册、登录&#xff1b; 2、登录后可以查看所有的注册的用户&#xff1b; 3、管理员操作对用…
阅读更多...
web 0基础第四节 多媒体标签

web 0基础第四节 多媒体标签

图片标签 主要是讲解 在html 中 怎么将图片放入其中 <!DOCTYPE html> <html lang"en"> <head> <meta charset"UTF-8"> <meta name"viewport" content"widthdevice-width, initial-scale1.0"> <…
阅读更多...
Spring Boot洗衣店订单系统：数据驱动的决策

Spring Boot洗衣店订单系统：数据驱动的决策

3系统分析 3.1可行性分析 通过对本洗衣店订单管理系统实行的目的初步调查和分析&#xff0c;提出可行性方案并对其一一进行论证。我们在这里主要从技术可行性、经济可行性、操作可行性等方面进行分析。 3.1.1技术可行性 本洗衣店订单管理系统采用JAVA作为开发语言&#xff0c;S…
阅读更多...
最新文章

Copyright @ 2022~2023