Java中的LinkedList
文章目录
- 前言
- 一、LinkedList的使用
- 1.1 什么是LinkedList
- 1.2 LinkedList的使用
- 1.2.1 LinkedList的构造
- 1.2.2 LinkedList的其他常用方法介绍
- 1.2.3 LinkedList的遍历
- 二、LinkedList的模拟实现
- 三、ArrayList和LinkedList的区别
- 总结
前言
上一节中我们讲解了Java中的链表，以及几个链表常见的面试题，浅提了一下LinkedList。接下来我们就来详细讲解Java中的LinkedList。
一、LinkedList的使用
1.1 什么是LinkedList
LinkedList官方文档
LinkedList的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，而是存储在单独的节点中，然后通过引用将节点连接起来了，因此在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。
在集合框架中，LinkedList也实现了List接口。
注意：
- LinkedList实现了List接口
- LinkedList的底层使用了双向链表
- LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问
- LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)
- LinkedList比较适合任意位置插入的场景
1.2 LinkedList的使用
1.2.1 LinkedList的构造
1.无参构造 LinkedList()
2.使用其他集合容器中的元素构造List public LinkedList(Collection<? extends E> c)
代码如下：
public static void main(String[] args) {
// 构造一个空的LinkedList
List<Integer> list1 = new LinkedList<>();
List<String> list2 = new java.util.ArrayList<>();
list2.add("JavaSE");
list2.add("JavaWeb");
list2.add("JavaEE");
// 使用ArrayList构造LinkedList
List<String> list3 = new LinkedList<>(list2);
}
1.2.2 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
代码如下：
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1); // add(elem): 表示尾插
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.add(6);
list.add(7);
System.out.println(list.size());
System.out.println(list);
// 在起始位置插入0
list.add(0, 0); // add(index, elem): 在index位置插入元素elem
System.out.println(list);
list.remove(); // remove(): 删除第一个元素，内部调用的是removeFirst()
list.removeFirst(); // removeFirst(): 删除第一个元素
list.removeLast(); // removeLast(): 删除最后元素
list.remove(1); // remove(index): 删除index位置的元素
System.out.println(list);
// contains(elem): 检测elem元素是否存在，如果存在返回true，否则返回false
if(!list.contains(1)){
list.add(0, 1);
}
list.add(1);
System.out.println(list);
System.out.println(list.indexOf(1)); // indexOf(elem): 从前往后找到第一个elem的位置
System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 从后往前找第一个1的位置
int elem = list.get(0); // get(index): 获取指定位置元素
list.set(0, 100); // set(index, elem): 将index位置的元素设置为elem
System.out.println(list);
// subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回
List<Integer> copy = list.subList(0, 3);
System.out.println(list);
System.out.println(copy);
list.clear(); // 将list中元素清空
System.out.println(list.size());
}
1.2.3 LinkedList的遍历
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1); // add(elem): 表示尾插
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.add(6);
list.add(7);
System.out.println(list.size());
// foreach遍历
for (int e:list) {
System.out.print(e + " ");
}
System.out.println();
// 使用迭代器遍历---正向遍历
ListIterator<Integer> it = list.listIterator();
while(it.hasNext()){
System.out.print(it.next()+ " ");
}
System.out.println();
// 使用反向迭代器---反向遍历
ListIterator<Integer> rit = list.listIterator(list.size());
while (rit.hasPrevious()){
System.out.print(rit.previous() +" ");
}
System.out.println();
}
二、LinkedList的模拟实现
代码如下：
public class MyLinkedList {
static class LinkedList {
public int val;
public LinkedList prev;
public LinkedList next;
public LinkedList(int val) {
this.val = val;
}
}
public LinkedList head;
public LinkedList last;
// 2、无头双向链表实现
//头插法
public void addFirst(int data){
LinkedList node = new LinkedList(data);
if(head==null) {
head = node;
last = node;
} else {
head.prev = node;
node.next = head;
head = node;
}
}
//尾插法
public void addLast(int data){
LinkedList node = new LinkedList(data);
if(head==null) {
head=node;
last=node;
} else {
last.next=node;
node.prev=last;
last = node;
}
}
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data){
if(index<0 || index>size()) {
System.out.println("位置不合法");
}
if(index==0) {
addLast(data);
return;
}
if(index==size()) {
addLast(data);
return;
}
LinkedList node = new LinkedList(data);
LinkedList cur = findIndex(index);
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev=node;
}
public LinkedList findIndex(int index) {
LinkedList cur = head;
while (index!=0) {
cur = cur.next;
index--;
}
return cur;
}
//查找是否包含关键字key是否在链表当中
public boolean contains(int key){
LinkedList cur = head;
while (cur!=null) {
if(cur.val==key) {
return true;
}
cur = cur.next;
}
return false;
}
//删除第一次出现关键字为key的节点
public void remove(int key){
LinkedList cur = head;
while (cur!=null) {
if(cur.val==key) {
//头节点
if(cur==head) {
head = head.next;
if (head!=null) {
head.prev = null;
}
} else {
//中间 节点和 尾部节点
cur.prev.next = cur.next;
if(cur.next!=null) {
//中间
cur.next.prev = cur.prev;
}else {
//尾部
last = last.prev;
}
}
return;
}
cur=cur.next;
}
}
//删除所有值为key的节点
public void removeAllKey(int key){
LinkedList cur = head;
while (cur!=null) {
if(cur.val==key) {
//头节点
if(cur==head) {
head = head.next;
if (head!=null) {
head.prev = null;
}
} else {
//中间 节点和 尾部节点
cur.prev.next = cur.next;
if(cur.next!=null) {
//中间
cur.next.prev = cur.prev;
}else {
//尾部
last = last.prev;
}
}
}
cur=cur.next;
}
}
//得到的长度
public int size(){
int len = 0;
LinkedList cur = head;
while (cur!=null) {
len++;
cur=cur.next;
}
return len;
}
public void display(){
LinkedList cur = head;
while (cur!=null) {
System.out.print(cur.val+" ");
cur=cur.next;
}
System.out.println();
}
public void clear(){
LinkedList cur = head;
while (cur!=null) {
LinkedList curNext = cur.next;
cur.prev = null;
cur.next = null;
cur = curNext;
}
head=null;;
last=null;
}
}
三、ArrayList和LinkedList的区别
- 在存储空间上，ArrayList在物理上一定连续，LinkedList在逻辑上连续，但物理上不一定连续
- ArrayList支持随机访问，时间复杂度为O(1)，但是LinkedList不支持，时间复杂度为O(N)
- ArrayList在头插时需要搬移元素，效率低O(N)，LinkedList只需要修改引用的指向，时间复杂度为O(1)
- ArrayList在插入时空间不够时需要扩容，但是LinkedList没有容量的概念
- ArrayList应用于“元素高效存储和频繁访问”，LinkedList应用于“任意位置插入和删除频繁”
总结
以上就是今天要讲的内容，本文介绍了LinkedList的使用以及其模拟实现，最后我们对比了ArrayList和LinkedList。