我的编程空间,编程开发者的网络收藏夹
学习永远不晚

Java数据结构之LinkedList从链表到实现

短信预约 -IT技能 免费直播动态提醒
省份

北京

  • 北京
  • 上海
  • 天津
  • 重庆
  • 河北
  • 山东
  • 辽宁
  • 黑龙江
  • 吉林
  • 甘肃
  • 青海
  • 河南
  • 江苏
  • 湖北
  • 湖南
  • 江西
  • 浙江
  • 广东
  • 云南
  • 福建
  • 海南
  • 山西
  • 四川
  • 陕西
  • 贵州
  • 安徽
  • 广西
  • 内蒙
  • 西藏
  • 新疆
  • 宁夏
  • 兵团
手机号立即预约

请填写图片验证码后获取短信验证码

看不清楚,换张图片

免费获取短信验证码

Java数据结构之LinkedList从链表到实现

1.ArrayList的缺陷

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
	// ...
	// 默认容量是10
	private static final int DEFAULT_CAPACITY = 10;
	//...
	// 数组:用来存储元素
	transient Object[] elementData; // non-private to simplify nested class access
	// 有效元素个数
	private int size;
	public ArrayList(int initialCapacity) {
		if (initialCapacity > 0) {
			this.elementData = new Object[initialCapacity];
		} else if (initialCapacity == 0) {
			this.elementData = EMPTY_ELEMENTDATA;
				} else {
						throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
				}
		} 
		// ...
}

由于其底层是一段连续空间,当在ArrayList任意位置插入或者删除元素时,就需要将后序元素整体往前或者往后搬移,时间复杂度为O(n),效率比较低,因此ArrayList不适合做任意位置插入和删除比较多的场景。因此:java集合中又引入了LinkedList,即链表结构

2.LinkedList

LinkedList概念

LinkedList的底层是双向链表结构,由于链表没有将元素存储在连续的空间中,元素存储在单独的节点中,然后通过引用将节点连接起来了,因此在在任意位置插入或者删除元素时,不需要搬移元素,效率比较高。

在集合框架中,LinkedList也实现了List接口,具体如下:

说明:

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

LinkedList的使用

LinkedList的构造

方法解释
LinkedList()无参构造
public LinkedList(Collection<? extends E> c)使用其他集合容器中元素构造List
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);
}

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 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位置插入元素elemSystem.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());
}

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();
}

3.链表的概念及结构

链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。

实际中链表的结构非常多样,以下情况组合起来就有8种链表结构:

  • 单向或者双向
  • 带头或者不带头
  • 循环或者非循环

虽然有这么多的链表的结构,但是我们重点掌握两种:

  • 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
  • 无头双向链表:在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

4.ArrayList和LinkedList的区别

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

到此这篇关于Java数据结构之LinkedList从链表到实现的文章就介绍到这了,更多相关Java LinkedList内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

Java数据结构之LinkedList从链表到实现

下载Word文档到电脑,方便收藏和打印~

下载Word文档

猜你喜欢

Java数据结构之LinkedList从链表到实现

LinkedList是Java中常用的数据结构之一,实现了链表的特性,支持快速添加、删除元素,可以用于实现队列、栈、双向队列等数据结构。LinkedList的内部实现采用了双向链表,其中每个节点都包含前驱节点和后继节点的引用,可以直接访问链表的头尾元素
2023-05-18

数据结构(Java实现)LinkedList与链表(上)

链表 逻辑结构 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。 无头双向链表:在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。
2023-08-30

Java数据结构之ArrayList从顺序表到实现

Java中的ArrayList是一种基于数组实现的数据结构,支持动态扩容和随机访问元素,可用于实现顺序表等数据结构。ArrayList在内存中连续存储元素,支持快速的随机访问和遍历。通过学习ArrayList的实现原理和使用方法,可以更好地掌握Java中的数据结构和算法
2023-05-18

Java数据结构之双向链表的实现

相较单链表,双向链表除了data与next域,还多了一个pre域用于表示每个节点的前一个元素。这样做给双向链表带来了很多优势。本文主要介绍了双向链表的实现,需要的可以参考一下
2022-11-13

TypeScript数据结构链表结构 LinkedList教程及面试

这篇文章主要为大家介绍了TypeScript数据结构链表结构 LinkedList教程及面试,有需要的朋友可以借鉴参考下,希望能够有所帮助,祝大家多多进步,早日升职加薪
2023-02-05

Java数据结构之双向链表如何实现

这篇文章主要讲解了“Java数据结构之双向链表如何实现”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“Java数据结构之双向链表如何实现”吧!双向链表(Doubly linked list)什
2023-06-30

用Python实现数据结构之链表

链表与栈,队列不一样,它是由一个个节点构成的,每个节点存储着本身的一些信息,也存储着其他一个或多个节点的引用,可以从一个节点找到其他的节点,节点与节点之间就像是有链连在一起一样,这种数据结构就叫做链表单向链表是链表的最简单形式,链表的第一个
2023-01-30

数据结构TypeScript之链表实现详解

这篇文章主要为大家介绍了数据结构TypeScript之链表实现详解,有需要的朋友可以借鉴参考下,希望能够有所帮助,祝大家多多进步,早日升职加薪
2023-01-30

Java数据结构之链表的概念及结构

这篇文章主要介绍了数据链表的概念及结构,链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。想进一步了解的同学,可以参考阅读本文
2023-05-14

C++数据结构之单链表如何实现

这篇文章主要介绍了C++数据结构之单链表如何实现的相关知识,内容详细易懂,操作简单快捷,具有一定借鉴价值,相信大家阅读完这篇C++数据结构之单链表如何实现文章都会有所收获,下面我们一起来看看吧。一、单链表的定义线性表的链式存储又称为单链表,
2023-06-30

Java数据结构之LinkedList的用法详解

链表(Linked list)是一种常见的基础数据结构,是一种线性表。Java的LinkedList(链表) 类似于 ArrayList,是一种常用的数据容器,本文就来简单讲讲它的使用吧
2023-05-19

python数据结构之链表

''''链表的实现,单向链表''''''建立节点'''class jd:    def __init__(self,data):        self.data = data        self.next = None'''实现链表的
2023-01-31

Java数据结构之双端链表原理与实现方法

本文实例讲述了Java数据结构之双端链表原理与实现方法。分享给大家供大家参考,具体如下:一、概述:1、什么时双端链表:链表中保持这对最后一个连点引用的链表2、从头部插入要对链表进行判断,如果为空则设置尾节点为新添加的节点3、从尾部进行插入如
2023-05-30

编程热搜

  • Python 学习之路 - Python
    一、安装Python34Windows在Python官网(https://www.python.org/downloads/)下载安装包并安装。Python的默认安装路径是:C:\Python34配置环境变量:【右键计算机】--》【属性】-
    Python 学习之路 - Python
  • chatgpt的中文全称是什么
    chatgpt的中文全称是生成型预训练变换模型。ChatGPT是什么ChatGPT是美国人工智能研究实验室OpenAI开发的一种全新聊天机器人模型,它能够通过学习和理解人类的语言来进行对话,还能根据聊天的上下文进行互动,并协助人类完成一系列
    chatgpt的中文全称是什么
  • C/C++中extern函数使用详解
  • C/C++可变参数的使用
    可变参数的使用方法远远不止以下几种,不过在C,C++中使用可变参数时要小心,在使用printf()等函数时传入的参数个数一定不能比前面的格式化字符串中的’%’符号个数少,否则会产生访问越界,运气不好的话还会导致程序崩溃
    C/C++可变参数的使用
  • css样式文件该放在哪里
  • php中数组下标必须是连续的吗
  • Python 3 教程
    Python 3 教程 Python 的 3.0 版本,常被称为 Python 3000,或简称 Py3k。相对于 Python 的早期版本,这是一个较大的升级。为了不带入过多的累赘,Python 3.0 在设计的时候没有考虑向下兼容。 Python
    Python 3 教程
  • Python pip包管理
    一、前言    在Python中, 安装第三方模块是通过 setuptools 这个工具完成的。 Python有两个封装了 setuptools的包管理工具: easy_install  和  pip , 目前官方推荐使用 pip。    
    Python pip包管理
  • ubuntu如何重新编译内核
  • 改善Java代码之慎用java动态编译

目录