首页 > 编程语言 >详解Java LinkedList

详解Java LinkedList

时间：2023-11-02 15:46:14浏览次数：39  
标签：Node prev Java LinkedList next 详解 null public

LinkedList简介

LinkedList是List接口的实现类，基于双向链表实现，继承自AbstractSequentialList类，同时也实现了Cloneable、Serializable接口。此外还实现了Queue和Deque接口，可以作为队列或双端队列使用。

image

LinkedList的插入删除时间复杂度：

  • 在头部或尾部插入删除元素，只需要修改头节点或尾节点的指针即可完成，时间复杂度为O(1)；
  • 在其他位置插入删除元素，需要遍历到指定位置，再修改指定节点的指针，平均要移动n/2个位置，时间复杂度为O(n)。

LinkedList没有像ArrayList有RandomAccess接口的标记，因为LinkedList基于链表实现，链表节点之间的内存地址不连续，只能通过指针来定位，因此无法实现快速随机访问。

常用方法

public class LinkedListTest {
    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<>();
		//添加元素
        linkedList.add(2);
        linkedList.addFirst(1);
        linkedList.add(3);
        linkedList.add(4);
        linkedList.addLast(5);
		//获取元素
        System.out.println(linkedList.get(1));
        System.out.println(linkedList.getFirst());
        System.out.println(linkedList.getLast());
		//创建双端队列
        Deque<String> deque = new LinkedList<>();
		//元素入队
        deque.offer("a");
        deque.offer("b");
        deque.offer("c");
		//获取队头元素，但不删除队头元素
        System.out.println(deque.peek());
		//元素出队
        String a = deque.poll();
        System.out.println(a);
    }
}

LinkedList核心源码分析

下面以JDK17的LinkedList代码进行分析。

类属性

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
	//LinkedList大小
    transient int size = 0;

    //首节点
    transient Node<E> first;

    //尾节点
    transient Node<E> last;
}

LinkedList中的节点由Node定义：

private static class Node<E> {
	E item; //节点值
	Node<E> next; //后继节点
	Node<E> prev; //前驱节点

	Node(Node<E> prev, E element, Node<E> next) {
		this.item = element;
		this.next = next;
		this.prev = prev;
	}
}

构造方法

//创建一个空链表对象
public LinkedList() {
}

//传入一个集合，将集合中的元素存入链表
public LinkedList(Collection<? extends E> c) {
	this();
	addAll(c);
}

添加元素

因为LinkedList基于双向链表实现，并且实现了List和Queue接口，所有有多种添加元素的方法。
add方法

//在链表尾部添加元素
public boolean add(E e) {
	linkLast(e);
	return true;
}

//尾插法
void linkLast(E e) {
	final Node<E> l = last;
	final Node<E> newNode = new Node<>(l, e, null);
	last = newNode;
	if (l == null)
		first = newNode;
	else
		l.next = newNode;
	size++;
	modCount++;
}

//在指定下标出添加元素
public void add(int index, E element) {
	//检查下标是否越界
	checkPositionIndex(index);
	//如果下标是最后位置则使用尾插法
	if (index == size)
		linkLast(element);
	else
		linkBefore(element, node(index));
}

//在指定节点之前插入元素
void linkBefore(E e, Node<E> succ) {
	// assert succ != null;
	final Node<E> pred = succ.prev;
	final Node<E> newNode = new Node<>(pred, e, succ);
	succ.prev = newNode;
	if (pred == null)
		first = newNode;
	else
		pred.next = newNode;
	size++;
	modCount++;
}

//插入链表头部
public void addFirst(E e) {
	linkFirst(e);
}
//头插法
private void linkFirst(E e) {
	final Node<E> f = first;
	final Node<E> newNode = new Node<>(null, e, f);
	first = newNode;
	if (f == null)
		last = newNode;
	else
		f.prev = newNode;
	size++;
	modCount++;
}

//插入链表尾部
public void addLast(E e) {
	linkLast(e);
}

获取元素

LinkedList提供了三个get方法获取元素。

//获取链表第一个元素
public E getFirst() {
	final Node<E> f = first;
	if (f == null)
		throw new NoSuchElementException();
	return f.item;
}

//获取链表最后一个元素
public E getLast() {
	final Node<E> l = last;
	if (l == null)
		throw new NoSuchElementException();
	return l.item;
}

//根据下标获取链表中的元素
public E get(int index) {
	//检查下标是否越界
	checkElementIndex(index);
	//遍历链表，返回查找到的节点值
	return node(index).item;
}

node方法就是用来遍历链表的：

Node<E> node(int index) {
	// assert isElementIndex(index);
	//如果下标小于LinkedList的一半则从头节点开始遍历，否则从尾节点开始
	if (index < (size >> 1)) {
		Node<E> x = first;
		for (int i = 0; i < index; i++)
			x = x.next;
		return x;
	} else {
		Node<E> x = last;
		for (int i = size - 1; i > index; i--)
			x = x.prev;
		return x;
	}
}

删除元素

removeFirst方法，删除链表头节点

public E removeFirst() {
	final Node<E> f = first;
	if (f == null)
		throw new NoSuchElementException();
	return unlinkFirst(f);
}

private E unlinkFirst(Node<E> f) {
	// assert f == first && f != null;
	//保留待删除节点的信息
	final E element = f.item;
	//记录待删除节点的后继
	final Node<E> next = f.next;
	f.item = null;
	f.next = null; // help GC
	first = next;
	if (next == null)
		last = null;
	else
		next.prev = null;
	size--;
	modCount++;
	return element;
}

removeLast方法，删除链表尾节点

public E removeLast() {
	final Node<E> l = last;
	if (l == null)
		throw new NoSuchElementException();
	return unlinkLast(l);
}

private E unlinkLast(Node<E> l) {
	// assert l == last && l != null;
	final E element = l.item;
	//记录待删除节点的前驱
	final Node<E> prev = l.prev;
	l.item = null;
	l.prev = null; // help GC
	last = prev;
	if (prev == null)
		first = null;
	else
		prev.next = null;
	size--;
	modCount++;
	return element;
}

public boolean remove(Object o) {
	if (o == null) {
		for (Node<E> x = first; x != null; x = x.next) {
			if (x.item == null) {
				unlink(x);
				return true;
			}
		}
	} else {
		for (Node<E> x = first; x != null; x = x.next) {
			if (o.equals(x.item)) {
				unlink(x);
				return true;
			}
		}
	}
	return false;
}

public E remove(int index) {
	checkElementIndex(index);
	return unlink(node(index));
}

//实际执行删除节点的方法
E unlink(Node<E> x) {
	// assert x != null;
	//保留待删除节点的信息，记录前驱和后继
	final E element = x.item;
	final Node<E> next = x.next;
	final Node<E> prev = x.prev;

	if (prev == null) {
		first = next;
	} else {
		prev.next = next;
		x.prev = null;
	}

	if (next == null) {
		last = prev;
	} else {
		next.prev = prev;
		x.next = null;
	}

	x.item = null;
	size--;
	modCount++;
	return element;
}

队列操作

返回队头元素：

public E peek() {
	final Node<E> f = first;
	return (f == null) ? null : f.item;
}

队头元素出队，调用了删除链表头节点的方法：

public E poll() {
	final Node<E> f = first;
	return (f == null) ? null : unlinkFirst(f);
}

入队，调用了add方法：

public boolean offer(E e) {
	return add(e);
}

此外还有一些双端队列的方法，如offerFirst、offerLast、peekFirst、peekLast、pollFirst、pollLast等。

标签：Node,prev,Java,LinkedList,next,详解,null,public
From： https://www.cnblogs.com/KRDecad3/p/17803102.html

相关文章

  • javaapi、spark、flink 创建Iceberg表，hive 和impala无法正常读取解决
    spark、flink创建Iceberg表中，元数据存储在hive的meta_store,发现hive或者impala无法正常读取报错。事实上解决方案是在spark、flink的SQL中执行语句:addiceberg相关引擎的runntime的jar;ALTERTABLEtSETTBLPROPERTIES('storage_handler'='org.apache.iceberg.mr.hive......
  • js/javaScript实现金额千分位
    作为前端开发，我们都知道，在实际的需求开发中，难免会遇到需要将接口返回的金额进行千分位格式化的场景。千分位后的金额便于阅读，提升用户体验。金额千分位可以由前端来处理，也可以后端处理后返回给前端展示。下边就来贴一下前端的两种实现方式：方法一：constcheckNaN=(value,cb)=......
  • Chromium VIZ架构详解
    1.VIZ的三个端在设计层面上viz的架构如下图所示：在设计上 viz 分了三个端，分别是client端,host端和service端。client 端用于生成要显示的画面(CF)。应用中至少有一个rootclient，可以有多个childclient，它们组成了一个client树，每个Client都有一个FrameSinkId......
  • java练习：二维码生成和输出
    <!--二维码生成--><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>2.2</version></dependency><dependency><groupId>com.google.zxing</groupId&......
  • Delphi使用TNetHTTPClient上传文件java接收测试
    Delphi使用TNetHTTPClient上传文件java接收测试上传客户端新建一个应用，拖入一个TButton按扭，一个TMemo多行文件显示框，一个TNetHttpClient,一个OpenDialog文件打开对话框。双击按扭添加代码  uses  System.Net.Mime;procedureTForm1.Button1Click(Sender:TObject);var......
  • 自动化构建工具make/makefile详解
    一、工具介绍1.1为什么需要使用自动化项目构建工具呢在我看来，在平时写较少代码，只有1个源文件的时候，用make和不用make感觉差别不大，但是当项目源文件一多，需要一个个的去输入gcc进行编译，显然是十分麻烦的。所以make这个工具可以极大的提高项目完成后的测试工作。1.2make/makefile介绍......
  • java语言基础
    在计算机编程中，标识符是用来代表变量、函数、类、模块等命名实体的名称。标识符可以包含字母、数字和下划线，并且必须遵循一些特定的规则和约定。以下是一些通用的标识符规则：只能以字母（包括大写和小写）、下划线(_)或者某些特殊字符（在某些编程语言中）开头。其余部分可以是字母......
  • Java 匿名函数的概念和写法
    匿名函数的实现1.定义一个函数式接口。只有一个抽象方法的接口就是函数式接口//1.定义一个函数式接口。只有一个抽象方法的接口就是函数式接口interfaceILike{voidhit(longparam);}没有类名，必须借助接口或父类通过实例化函数式接口就可以完成匿名内部类实现此接口......
  • Java语言基础知识点梳理与总结
    Java语言基础知识点梳理与总结Java是一种广泛应用于软件开发的编程语言，具有丰富的特性和功能。在学习Java语言时，了解以下基础知识点对于建立坚实的编程基础非常重要。本博客将介绍Java语言中的标识符、运算符、流程控制、循环结构、分支结构、数组、方法、类与对象等主要知识点。......
  • Java踩坑之List的removeAll方法
    最近写个功能，需要用到差集，然后就想到了javaList中有一个removeAll方法，正好可以实现差集功能，可以直接调用。我们知道，apache的common-collections包下面得CollectionUtils.subtract()方法也可以对List作差集，为了比较两种方式差集的结果，见Java中CollectionUtils.subtract()......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99