数据结构 - 3(链表12000字详解)

2023-10-14 18:21

本文主要是介绍数据结构 - 3(链表12000字详解),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一:LinkedList的使用

1.1 ArrayList的缺陷

上篇文章我们已经基本熟悉了ArrayList的使用,并且进行了简单模拟实现。由于其底层是一段连续空间,当在ArrayList任意位置插入或者删除元素时,就需要将后序元素整体往前或者往后搬移,时间复杂度为O(n),效率比较低,因此ArrayList不适合做任意位置插入和删除比较多的场景。因此:java集合中又引入了LinkedList,即链表结构。

1.2 链表的概念及结构

链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
在这里插入图片描述
在这里插入图片描述
实际中链表的结构非常多样,以下情况组合起来就有8种链表结构:

  • 单向或者双向
    在这里插入图片描述
  • 带头或者不带头
    在这里插入图片描述
  • 循环或者非循环
    在这里插入图片描述

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

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

在这里插入图片描述

  • 无头双向链表:在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

1.3 LinkedList的使用

LinkedList的底层是双向链表结构(链表后面介绍),由于链表没有将元素存储在连续的空间中,元素存储在单独的节点中,然后通过引用将节点连接起来了,因此在在任意位置插入或者删除元素时,不需要搬移元素,效率比较高。
在这里插入图片描述
在集合框架中,LinkedList也实现了List接口,具体如下:
在这里插入图片描述
【说明】

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

1.4 LinkedList的构造方法

LinkedList的构造方法

方法解释
LinkedList()无参构造
public LinkedList(Collection<? extends E> c)使用其他集合容器中元素构造List

public LinkedList(Collection<? extends E> c) 是 Java 中 LinkedList 类的一个构造方法。它的作用是创建一个新的 LinkedList 对象,并将指定集合中的所有元素添加到该链表中。

下面是代码示例:

List<String> list1 = new ArrayList<>();
list1.add("Apple");
list1.add("Banana");
list1.add("Orange");LinkedList<String> linkedList = new LinkedList<>(list1);

在这个例子中,我们先创建了一个 ArrayList 类型的集合 list1,并向其中添加了三个字符串元素。然后我们使用 LinkedList 的构造方法将 list1 转换为一个新的 LinkedList 对象,并将 list1 中的所有元素添加到链表中。

1.5 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<>();// add(elem): 表示尾插list.add(1); 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);// add(index, elem): 在index位置插入元素elemlist.add(0, 0);  System.out.println(list);// remove(): 删除第一个元素,内部调用的是removeFirst()list.remove();     // removeFirst(): 删除第一个元素list.removeFirst();   // removeLast(): 删除最后元素list.removeLast();   // remove(index): 删除index位置的元素list.remove(1); System.out.println(list);// contains(elem): 检测elem元素是否存在,如果存在返回true,否则返回falseif(!list.contains(1)){list.add(0, 1);}
list.add(1);System.out.println(list);// indexOf(elem): 从前往后找到第一个elem的位置System.out.println(list.indexOf(1));  // lastIndexOf(elem): 从后往前找第一个1的位置System.out.println(list.lastIndexOf(1)); // get(index): 获取指定位置元素int elem = list.get(0);  // set(index, elem): 将index位置的元素设置为elemlist.set(0, 100);     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中元素清空list.clear();        System.out.println(list.size());
}

1.6ArrayList和LinkedList的区别

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

二:LinkedList模拟实现

2.1无头单向非循环链表

// 1、无头单向非循环链表实现
public class SingleLinkedList {//头插法public void addFirst(int data){}//尾插法public void addLast(int data){}//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data){}//查找是否包含关键字key是否在单链表当中public boolean contains(int key){return false;}//删除第一次出现关键字为key的节点public void remove(int key){}
//删除所有值为key的节点public void removeAllKey(int key){}//得到单链表的长度public int size(){return -1;}//清空链表public void clear() {}//打印链表public void display() {}
}

下面是模拟实现后的代码:


public class SingleLinkedList {private Node head; // 链表头节点// 节点类private class Node {int data;Node next;public Node(int data) {this.data = data;this.next = null;}}// 头插法,在链表头部插入新节点public void addFirst(int data) {Node newNode = new Node(data); // 创建一个新节点newNode.next = head; // 将新节点的next指向当前头节点head = newNode; // 将新节点设置为头节点}// 尾插法,在链表尾部插入新节点public void addLast(int data) {Node newNode = new Node(data); // 创建一个新节点if (head == null) { // 如果链表为空,将新节点设置为头节点并返回head = newNode;return;}Node curr = head; // 从头节点开始遍历链表,找到最后一个节点while (curr.next != null) {curr = curr.next;}curr.next = newNode; // 将新节点链接到最后一个节点的next上}// 任意位置插入,在指定位置插入新节点public void addIndex(int index, int data) {if (index < 0 || index > size()) { // 检查插入位置的合法性throw new IndexOutOfBoundsException("Index out of range"); // 抛出越界异常}if (index == 0) { // 如果插入位置是头部,调用addFirst方法addFirst(data);} else if (index == size()) { // 如果插入位置是尾部,调用addLast方法addLast(data);} else { // 在指定位置插入新节点Node newNode = new Node(data); // 创建新节点Node prev = getNode(index - 1); // 获取插入位置前一个节点newNode.next = prev.next; // 将新节点的next指向插入位置节点的nextprev.next = newNode; // 插入位置节点的next指向新节点}}// 查找是否包含关键字keypublic boolean contains(int key) {Node curr = head; // 从头节点开始遍历链表while (curr != null) {if (curr.data == key) { // 如果节点的data等于关键字key,返回truereturn true;}curr = curr.next; // 继续向下一个节点遍历}return false; // 遍历完链表都没有找到关键字key,返回false}// 删除第一次出现关键字为key的节点public void remove(int key) {if (head == null) { // 如果链表为空,直接返回return;}if (head.data == key) { // 如果头节点的data等于关键字key,将头节点指向下一个节点并返回head = head.next;return;}Node prev = head; // 设置prev指针指向头节点Node curr = head.next; // 设置curr指针指向头节点的下一个节点while (curr != null) { // 从头节点的下一个节点开始遍历链表if (curr.data == key) { // 如果节点的data等于关键字key,将prev节点的next指向当前节点的下一个节点并返回prev.next = curr.next;return;}prev = curr; // prev和curr指针向后移动curr = curr.next;}}// 删除所有值为key的节点public void removeAllKey(int key) {if (head == null) { // 如果链表为空,直接返回return;}// 处理头节点为key的情况while (head != null && head.data == key) { // 如果头节点的data等于关键字key,将头节点指向下一个节点head = head.next;}Node prev = head; // 设置prev指针指向头节点Node curr = head != null ? head.next : null; // 设置curr指针指向头节点的下一个节点while (curr != null) { // 从头节点的下一个节点开始遍历链表if (curr.data == key) { // 如果节点的data等于关键字key,将prev节点的next指向当前节点的下一个节点prev.next = curr.next;} else { // 否则prev指针和curr指针向后移动prev = curr;}curr = curr.next;}}// 得到单链表的长度public int size() {int count = 0; // 计数变量Node curr = head; // 从头节点开始遍历链表while (curr != null) {count++; // 每遍历一个节点,计数器加一curr = curr.next; // 移动到下一个节点}return count; // 返回计数器的值}// 清空链表public void clear() {head = null; // 将头节点置为null}// 获取指定位置上的节点private Node getNode(int index) {if (index < 0 || index >= size()) { // 检查索引的合法性throw new IndexOutOfBoundsException("Index out of range"); // 抛出越界异常}Node curr = head; // 从头节点开始遍历链表for (int i = 0; i < index; i++) { // 遍历到指定位置的节点curr = curr.next;}return curr; // 返回指定位置的节点}// 打印链表public void display() {Node curr = head; // 从头节点开始遍历链表while (curr != null) {System.out.print(curr.data + " "); // 打印当前节点的数据curr = curr.next; // 移动到下一个节点}System.out.println(); // 换行}public static void main(String[] args) {SingleLinkedList list = new SingleLinkedList();list.addFirst(1); // 在链表头部插入节点 1list.addLast(3);  // 在链表尾部插入节点 3list.addIndex(1, 2); // 在下标为 1 的位置插入节点 2list.display(); // 打印链表:1 2 3System.out.println("Contains 2: " + list.contains(2)); // 判断链表是否包含关键字 2,结果为 truelist.remove(2); // 删除首次出现的关键字为 2 的节点list.display(); // 打印链表:1 3list.addLast(1);list.addLast(2);list.addLast(3);list.display(); // 打印链表:1 3 1 2 3list.removeAllKey(1); // 删除所有值为 1 的节点list.display(); // 打印链表:3 2 3System.out.println("Size: " + list.size()); // 获取链表长度,结果为 3list.clear(); // 清空链表list.display(); // 打印链表:空}
}

2.2 无头双向非循环链表

// 2、无头双向链表实现
public class MyLinkedList {//头插法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 display(){}//清空public void clear(){}
}

下面是模拟实现后的代码:

// 2、无头双向链表实现
public class MyLinkedList {// 节点类private class Node {private int data; // 节点存储的数据private Node prev; // 前一个节点的引用private Node next; // 下一个节点的引用public Node(int data) {this.data = data; // 初始化节点的数据为传入的datathis.prev = null; // 初始化前一个节点的引用为nullthis.next = null; // 初始化下一个节点的引用为null}}private Node head; // 头节点private Node tail; // 尾节点private int size; // 链表长度// 头插法public void addFirst(int data) {Node newNode = new Node(data); // 创建一个新节点,存储传入的数据if (head == null) { // 如果头节点为null,说明链表为空head = newNode; // 将头节点指向新节点tail = newNode; // 将尾节点指向新节点} else { // 链表不为空newNode.next = head; // 将新节点的下一个节点指向当前头节点head.prev = newNode; // 将当前头节点的前一个节点指向新节点head = newNode; // 将头节点指向新节点}size++; // 链表长度加1}// 尾插法public void addLast(int data) {Node newNode = new Node(data); // 创建一个新节点,存储传入的数据if (tail == null) { // 如果尾节点为null,说明链表为空head = newNode; // 将头节点指向新节点tail = newNode; // 将尾节点指向新节点} else { // 链表不为空tail.next = newNode; // 将当前尾节点的下一个节点指向新节点newNode.prev = tail; // 将新节点的前一个节点指向当前尾节点tail = newNode; // 将尾节点指向新节点}size++; // 链表长度加1}// 任意位置插入,第一个数据节点为0号下标public void addIndex(int index, int data) {if (index < 0 || index > size) { // 如果索引小于0或者大于链表长度,抛出索引超出范围的异常throw new IndexOutOfBoundsException("Index out of bound");}if (index == 0) { // 如果要插入的位置是头节点前面,即插入为头节点addFirst(data); // 使用头插法} else if (index == size) { // 如果要插入的位置是尾节点后面,即插入为尾节点addLast(data); // 使用尾插法} else { // 在中间位置插入节点Node newNode = new Node(data); // 创建一个新节点,存储传入的数据Node currNode = goToIndex(index); // 找到要插入位置的前一个节点newNode.prev = currNode.prev; // 将新节点的前一个节点指向要插入位置的前一个节点newNode.next = currNode; // 将新节点的下一个节点指向要插入位置的节点currNode.prev.next = newNode; // 将要插入位置的前一个节点的下一个节点指向新节点currNode.prev = newNode; // 将要插入位置的节点的前一个节点指向新节点size++; // 链表长度加1}}// 查找是否包含关键字key是否在单链表当中public boolean contains(int key) {Node currNode = head; // 从头节点开始查找while (currNode != null) { // 当前节点不为nullif (currNode.data == key) { // 如果当前节点的数据等于关键字return true; // 返回true}currNode = currNode.next; // 继续下一个节点}return false; // 没找到关键字,返回false}// 删除第一次出现关键字为key的节点public void remove(int key) {Node currNode = head; // 从头节点开始查找while (currNode != null) { // 当前节点不为nullif (currNode.data == key) { // 如果当前节点的数据等于关键字if (currNode == head) { // 如果当前节点是头节点head = currNode.next; // 将头节点指向当前节点的下一个节点if (head != null) {head.prev = null; // 如果头节点不为null,将新头节点的前一个节点设置为null}if (currNode == tail) { // 如果当前节点是尾节点tail = null; // 将尾节点置为null}} else if (currNode == tail) { // 如果当前节点是尾节点tail = currNode.prev; // 将尾节点指向当前节点的前一个节点tail.next = null; // 将新尾节点的下一个节点设置为null} else { // 在中间位置删除节点currNode.prev.next = currNode.next; // 将要删除节点的前一个节点的下一个节点指向要删除节点的下一个节点currNode.next.prev = currNode.prev; // 将要删除节点的下一个节点的前一个节点指向要删除节点的前一个节点}size--; // 链表长度减1return; // 删除完成,结束方法}currNode = currNode.next; // 继续下一个节点}}// 删除所有值为key的节点public void removeAllKey(int key) {Node currNode = head; // 从头节点开始查找while (currNode != null) { // 当前节点不为nullif (currNode.data == key) { // 如果当前节点的数据等于关键字if (currNode == head) { // 如果当前节点是头节点head = currNode.next; // 将头节点指向当前节点的下一个节点if (head != null) {head.prev = null; // 如果头节点不为null,将新头节点的前一个节点设置为null}if (currNode == tail) { // 如果当前节点是尾节点tail = null; // 将尾节点置为null}currNode = head; // 将当前节点指向新的头节点} else if (currNode == tail) { // 如果当前节点是尾节点tail = currNode.prev; // 将尾节点指向当前节点的前一个节点tail.next = null; // 将新尾节点的下一个节点设置为nullcurrNode = null; // 将当前节点置为null,用于结束循环} else { // 在中间位置删除节点currNode.prev.next = currNode.next; // 将要删除节点的前一个节点的下一个节点指向要删除节点的下一个节点currNode.next.prev = currNode.prev; // 将要删除节点的下一个节点的前一个节点指向要删除节点的前一个节点Node tempNode = currNode.next; // 保存需要删除的节点的下一个节点的引用currNode.next = null; // 将要删除节点的下一个节点置为nullcurrNode.prev = null; // 将要删除节点的前一个节点置为nullcurrNode = tempNode; // 将当前节点指向保存的下一个节点}size--; // 链表长度减1} else {currNode = currNode.next; // 继续下一个节点}}}// 得到双向链表的长度public int size() {return size; // 返回链表的长度}// 辅助函数,用于定位到指定索引的节点private Node goToIndex(int index) {Node currNode = head; // 从头节点开始int count = 0; // 计数器,记录已经遍历的节点个数while (count < index) { // 当计数器小于索引时currNode = currNode.next; // 继续下一个节点count++; // 计数器加1}return currNode; // 返回找到的节点}// 清空双向链表public void clear() {head = null; // 将头节点置为nulltail = null; // 将尾节点置为nullsize = 0; // 链表长度置为0}// 打印双向链表public void display() {Node currNode = head; // 从头节点开始while (currNode != null) { // 当前节点不为nullSystem.out.print(currNode.data + " "); // 打印当前节点的数据currNode = currNode.next; // 继续下一个节点}System.out.println(); // 换行}public static void main(String[] args) {MyLinkedList list = new MyLinkedList(); // 创建一个新的双向链表对象list.addFirst(1); // 在链表头插入数据1list.addLast(2); // 在链表尾插入数据2list.addIndex(1, 3); // 在索引1处插入数据3list.display(); // 输出:1 3 2System.out.println(list.contains(2)); // 输出:truelist.remove(3); // 删除数据3list.display(); // 输出:1 2list.removeAllKey(2); // 删除所有值为2的节点list.display(); // 输出:1list.clear(); // 清空链表System.out.println(list.size()); // 输出:0}
}

2.3LinkedList的遍历

当我们使用Java中的LinkedList类时,有几种方式可以进行遍历。我们可以使用foreach循环,也可以使用迭代器对链表进行正向和反向遍历。下面是代码示例:

首先,让我们创建一个LinkedList对象并向其添加一些元素

import java.util.LinkedList;public class LinkedListTraversal {public static void main(String[] args) {LinkedList<String> linkedList = new LinkedList<>();linkedList.add("Apple");linkedList.add("Banana");linkedList.add("Cherry");linkedList.add("Durian");}
}
  1. 使用foreach循环遍历

使用foreach循环可以直接遍历LinkedList中的元素。在每次迭代中,我们可以通过一个变量来访问当前元素。下面是使用foreach循环遍历LinkedList的示例代码:

for (String fruit : linkedList) {System.out.println(fruit);
}

输出结果为:

Apple
Banana
Cherry
Durian
  1. 使用迭代器进行正向遍历

LinkedList实现了Iterable接口,因此我们可以使用迭代器在链表上进行正向遍历。通过调用iterator()方法,我们可以获取一个Iterator对象,然后使用hasNext()next()方法来迭代遍历链表中的元素。下面是使用迭代器进行正向遍历的示例代码:

Iterator<String> iterator = linkedList.iterator();
while (iterator.hasNext()) {String fruit = iterator.next();System.out.println(fruit);
}

输出结果为:

Apple
Banana
Cherry
Durian
  1. 使用迭代器进行反向遍历

LinkedList还提供了一个descendingIterator()方法,返回一个逆向迭代器,使我们可以反向遍历链表中的元素。通过调用hasNext()next()方法,我们可以从尾部开始向前迭代遍历LinkedList。下面是使用迭代器进行反向遍历的示例代码:

Iterator<String> descendingIterator = linkedList.descendingIterator();
while (descendingIterator.hasNext()) {String fruit = descendingIterator.next();System.out.println(fruit);
}

输出结果为:

Durian
Cherry
Banana
Apple

以上就是LinkedList遍历的三种方式!

这篇关于数据结构 - 3(链表12000字详解)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/212308

相关文章

Linux线程同步/互斥过程详解

《Linux线程同步/互斥过程详解》文章讲解多线程并发访问导致竞态条件,需通过互斥锁、原子操作和条件变量实现线程安全与同步,分析死锁条件及避免方法,并介绍RAII封装技术提升资源管理效率... 目录01. 资源共享问题1.1 多线程并发访问1.2 临界区与临界资源1.3 锁的引入02. 多线程案例2.1 为

Python使用Tenacity一行代码实现自动重试详解

《Python使用Tenacity一行代码实现自动重试详解》tenacity是一个专为Python设计的通用重试库,它的核心理念就是用简单、清晰的方式,为任何可能失败的操作添加重试能力,下面我们就来看... 目录一切始于一个简单的 API 调用Tenacity 入门:一行代码实现优雅重试精细控制:让重试按我

Python标准库之数据压缩和存档的应用详解

《Python标准库之数据压缩和存档的应用详解》在数据处理与存储领域,压缩和存档是提升效率的关键技术,Python标准库提供了一套完整的工具链,下面小编就来和大家简单介绍一下吧... 目录一、核心模块架构与设计哲学二、关键模块深度解析1.tarfile:专业级归档工具2.zipfile:跨平台归档首选3.

idea的终端(Terminal)cmd的命令换成linux的命令详解

《idea的终端(Terminal)cmd的命令换成linux的命令详解》本文介绍IDEA配置Git的步骤:安装Git、修改终端设置并重启IDEA,强调顺序,作为个人经验分享,希望提供参考并支持脚本之... 目录一编程、设置前二、前置条件三、android设置四、设置后总结一、php设置前二、前置条件

python中列表应用和扩展性实用详解

《python中列表应用和扩展性实用详解》文章介绍了Python列表的核心特性:有序数据集合,用[]定义,元素类型可不同,支持迭代、循环、切片,可执行增删改查、排序、推导式及嵌套操作,是常用的数据处理... 目录1、列表定义2、格式3、列表是可迭代对象4、列表的常见操作总结1、列表定义是处理一组有序项目的

python使用try函数详解

《python使用try函数详解》Pythontry语句用于异常处理,支持捕获特定/多种异常、else/final子句确保资源释放,结合with语句自动清理,可自定义异常及嵌套结构,灵活应对错误场景... 目录try 函数的基本语法捕获特定异常捕获多个异常使用 else 子句使用 finally 子句捕获所

C++11范围for初始化列表auto decltype详解

《C++11范围for初始化列表autodecltype详解》C++11引入auto类型推导、decltype类型推断、统一列表初始化、范围for循环及智能指针,提升代码简洁性、类型安全与资源管理效... 目录C++11新特性1. 自动类型推导auto1.1 基本语法2. decltype3. 列表初始化3

SQL Server 中的 WITH (NOLOCK) 示例详解

《SQLServer中的WITH(NOLOCK)示例详解》SQLServer中的WITH(NOLOCK)是一种表提示,等同于READUNCOMMITTED隔离级别,允许查询在不获取共享锁的情... 目录SQL Server 中的 WITH (NOLOCK) 详解一、WITH (NOLOCK) 的本质二、工作

springboot自定义注解RateLimiter限流注解技术文档详解

《springboot自定义注解RateLimiter限流注解技术文档详解》文章介绍了限流技术的概念、作用及实现方式,通过SpringAOP拦截方法、缓存存储计数器,结合注解、枚举、异常类等核心组件,... 目录什么是限流系统架构核心组件详解1. 限流注解 (@RateLimiter)2. 限流类型枚举 (

Java Thread中join方法使用举例详解

《JavaThread中join方法使用举例详解》JavaThread中join()方法主要是让调用改方法的thread完成run方法里面的东西后,在执行join()方法后面的代码,这篇文章主要介绍... 目录前言1.join()方法的定义和作用2.join()方法的三个重载版本3.join()方法的工作原