数据结构教程系列03:如何在Java中使用链接列表

作者 : IT 大叔 本文共4480个字,预计阅读时间需要12分钟 发布时间: 2020-09-9

数据结构教程系列

数据结构教程系列01:JavaScript数组教程

数据结构教程系列02:使用Java深入研究树

数据结构教程系列03:如何在Java中使用链接列表

数据结构教程系列04:在JavaScript中引入图

数据结构教程系列05:在JavaScript中实现哈希表

数据结构教程系列06:如何在Java中使用堆栈和队列

对数据结构的良好理解是每个程序员在其工具包中拥有的一项重要技能。更不用说与链接列表有关的问题在大多数编码访谈中都很常见。

这些技能证明了您解决模棱两可的问题,复杂思考和识别代码中模式的能力。数据结构用于组织数据并将算法应用于代码。Java平台提供了各种数据结构的高性能实现,并且它是面试中最常用的测试编程语言之一。

今天,我们将研究一种这样的实现,即Linked List类。我们将研究它的工作原理,并学习如何使用它来存储和处理数据。

我们将介绍:

  • 什么是链表?
  • 如何创建和使用链接列表
  • 使用链表之前应考虑的事项
  • 摘要和资源

主数据结构,用于通过动手实践对访谈进行编码

什么是链表?

链表是由节点链组成的常见数据结构。每个节点都包含一个值和一个指向链中下一个节点的指针。头指针指向第一个节点,列表的最后一个元素指向空。当列表为空时,头指针指向空。

数据结构教程系列03:如何在Java中使用链接列表插图

链接列表可以动态增加大小。从链接列表中插入和删除很容易,因为与数组不同,因为我们只需要更改上一个元素和下一个元素的指针即可插入或删除一个元素。链接列表的一些重要应用包括:

  • 实施HashMap,文件系统和邻接列表
  • 动态内存分配:使用空闲块的链接列表
  • 对长整数执行算术运算
  • 维护名称目录

链表的类型

由于链表是线性数据结构,这意味着元素不会存储在连续的位置,因此有必要使用不同类型的链表来相应地访问和修改我们的元素。有三种不同类型的链接列表,它们可用于组织代码的不同目的。让我们来看看。

数据结构教程系列03:如何在Java中使用链接列表插图(2)

单链表(单向)

单链列表是单向的,这意味着它只能从头到最后一个节点(尾)在一个方向上遍历。单链接列表的一些常见操作是:

数据结构教程系列03:如何在Java中使用链接列表插图(4)

数据结构教程系列03:如何在Java中使用链接列表插图(6)

双链表(双向)

双链表(DLL)是基本链表的扩展,但是它们包含指向下一个节点以及上一个节点的指针。这确保了可以在两个方向上遍历该列表。DLL节点具有三个基本成员:

  • 数据
  • 指向下一个节点的指针
  • 指向上一个节点的指针

循环链表

循环链表循环运行:第一个元素指向最后一个元素,最后一个元素指向第一个元素。单链表和双链表可以制成循环链表。循环链表最重要的操作是:

  • insert-在列表的开头插入元素
  • 显示-显示列表
  • delete-从列表的开头删除元素

单链表的结构

在Java中,链接列表类是一个有序集合,其中包含许多相同类型的对象。链表中的数据存储在一系列容器中。该列表包含对第一个容器的引用,并且每个容器都具有到序列中下一个容器的链接。Java中的链接列表实现了抽象列表接口,并从中继承了各种构造函数和方法。此顺序数据结构可以用作列表,堆栈或队列。

数据结构教程系列03:如何在Java中使用链接列表插图(8)

正如我之前简要讨论过的,链表是由像链一样链接在一起的节点形成的。每个节点都保存数据,以及指向列表中下一个节点的指针。下图显示了单链表的理论。

数据结构教程系列03:如何在Java中使用链接列表插图(10)

要实现链接列表,我们需要以下两个类:

类节点

Node类将数据存储在单个节点中。它可以存储原始数据,例如整数和字符串,以及具有多个属性的复杂对象。除数据外,它还存储指向列表中下一个元素的指针,这有助于将节点像链一样链接在一起。这是Node类的典型定义:

//Class node having Generic data-type <T>
public class Node<T> {
  public T data; //Data to store (could be int, string, Object etc)
  public Node nextNode; //Pointer to next node in list
}

类链接列表

如上所述,单链接列表由像链一样链接在一起的节点组成。现在要访问此链,我们需要一个指针来跟踪列表的第一个元素。只要我们有关于第一个元素的信息,我们就可以遍历列表的其余部分而不必担心记住它们的存储位置。

单链接列表包含一个头节点:指向列表的第一个元素的指针。每当我们要遍历列表时,都可以使用此头节点来遍历。下面是单链接列表类的基本结构:

public class SinglyLinkedList<T> {
    //Node inner class for SLL
    public class Node{
        public T data; //Data to store (could be int, string, Object etc)
        public Node nextNode; //Pointer to next node in list

    }

    public Node headNode; //head node of the linked list
    public int size;      //size of the list

    //constructor
    public SinglyLinkedList() {
        headNode = null;
        size = 0;
    }
}

如何创建和使用链接列表

链接列表遵循线性结构,因此非常易于使用。它们与数组非常相似,但是链接列表不是静态的,因为每个元素都是其自己的对象。这是Java链表类的声明:

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, Serializable 

让我们在代码中看到更详细的示例。这是我们用Java创建基本链接列表的方式:

import java.util.LinkedList;

class Main {
  public static void main(String[] args) {
    LinkedList<String> names = new LinkedList<String>();
  }
}

链接列表类包含在Java.util包中。为了使用该类,我们需要在代码中导入包。我们已经使用new关键字初始化了一个空的链表。链表可以容纳任何类型的对象,包括null

将元素添加到链接列表

为了将元素添加到列表中,我们可以使用.add()方法。此方法采用一个元素(作为参数传递)并将其附加到列表的末尾。

import java.util.LinkedList;

class Main {
  public static void main(String[] args) {
    LinkedList<String> names = new LinkedList<String>();
    names.add("Brian");
    names.add("June");
    System.out.println(names); // This will output [Brian, June]
  }
}

如果要将新元素添加到特定位置,则可以通过将索引值作为方法的第一个参数传递来进行.add()

names.add(1, "Kathy");
System.out.println(names);
// Outputs [Brian, Kathy, June]

上面的代码行在names列表中的1位置或索引处插入“ Kathy” 。由于列表中的第一个元素具有索引0,因此将在“ Brian”之后和“ June”之前插入“ Kathy”。如果您使用过JavaScript中的Arrays,这会感到很熟悉。因为链接列表像JavaScript数组一样被索引,所以这种现象是可能的。

还有一些方法可以将元素显式添加到列表的末尾或开头。

names.addFirst("Luke");
names.addLast("Harry");
System.out.println(names);
// Outputs [Luke, Brian, Kathy, June, Harry]

.addFirst()方法将指定的元素添加到列表的开头。要在列表的末尾位置添加元素,请使用.addLast()方法。在上面的代码块中,“ Luke”被插入到列表中,并且成为列表中的第一个元素(现在具有index 0)。元素“ Harry”插入到末尾,使其成为列表中的最后一个元素。

继续学习。

从LinkedList中删除元素

与元素添加类似,“链接列表”提供了用于删除列表中元素的方法。这些方法在操作上类似于将元素添加到列表的方法。该.remove()方法删除指定元素的第一次出现。

names.remove("Brian"); // This will remove the first occurrence of "Brian" in the LinkedList

此方法类似于该.add()方法,因为它允许删除特定索引处的元素。调用names.remove(2)将删除index处的元素,该元素2在此列表中为“ Brian”。也可以分别使用.removeFirst().removeLast()方法删除列表中的第一个元素和最后一个元素。

names.removeFirst();
names.removeLast();

更新LinkedList中的元素

链接列表类提供了一种更改列表中元素的方法。此方法称为.set(),它获取一个索引和需要插入的元素,以替换该位置的上一个元素。

// names list is: [Kathy, June]
names.set(0, "Katherine");
// names list is: [Katherine, June]

遍历LinkedList

有两种方法可以迭代LinkedList中的元素。在下面的示例中,我们使用for循环和.get()链表的方法。

for (int i = 0; i < names.size(); i++) {
  System.out.println(names.get(i));
}

我们还可以使用foreach循环遍历链接列表。

for (String str : names) {
  System.out.println(str);
}

使用链表之前应考虑的事项

链表充当动态数组。这意味着我们不必在创建时指定大小,添加和删除元素时其大小会自动更改。链表类也使用双链表数据结构实现。这意味着列表中的每个元素都包含对其之前和之后的元素的引用。如果元素是列表中的最后一个元素,则其下一个引用将返回null

这种设计使“链接列表”在以下情况下很有用:

  • 您只能通过遍历列表来使用列表,而不是访问随机元素
  • 您经常需要从列表的开头或中间添加和删除元素

此设计还通过以下方式使LinkedList比较不利于ArrayList,后者通常是Java中的默认List实现:

  • 它使用的内存要比ArrayList它的项目引用所使用的存储空间多,一个用于上一个项目,另一个用于下一个项目
  • 由于链表本质上是顺序访问,因此必须从头(或尾)开始按顺序读取链表中的元素

摘要和资源

祝贺您学习了Java的“链表”类的基础知识。选择使用任何数据结构以及计算机编程中的任何方法都应取决于您要解决的问题。

要掌握Java中的喜欢列表,还有很多东西要学习和练习。以下是链表常见的数据结构面试挑战:

  • 插入单链接列表(末尾插入)
  • 在单链列表中搜索
  • 查找链接列表的长度
  • 在链接列表中检测循环
  • 从链接列表中删除重复项
  • 查找双链表是否是回文
免责声明:
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » 数据结构教程系列03:如何在Java中使用链接列表

常见问题FAQ

没有金币/金币不足 怎么办?
本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
所有资源普通会员都能下载吗?
本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。

发表评论