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

什么是链表？

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

单链表的结构

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

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

要实现链接列表，我们需要以下两个类：

类节点

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]

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

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

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

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

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