链表简介(Java实现)
链表是一个线性数据结构，包含一个元素序列，这样每个元素都可以引用序列中的下一个元素。
链接列表中的每个元素称为"节点"。
每个节点都包含一个数据元素和一个下一个Node，它指向链表中的下一个节点。
在链接列表中，我们可以根据需要创建任意数量的节点。
为什么我们需要一个链表？
尽管您可能早先已经看过Arrays数据结构，但它们也是线性数据结构，但是它们具有某些局限性，例如：
它们本质上是静态的，因此它们的大小无法更改。
他们需要连续的内存来存储其值。
解决这些限制链接列表提供以下功能：
动态内存分配，即编译器在运行时完成内存分配。
每个单独的节点可以具有任何内存块，并且通过该块的地址链接到其他节点，因此不需要连续的内存块。
链表的一般实现
链表
链接列表类包含一个私有类Node和一个Node对象类(称为Head)作为其属性之一。
Node头指向链接列表的开始。
每个节点都包含一个数据元素和一个下一个节点，该节点指向链接列表中的下一个节点。
最后的节点指向空。
在较新的变体中，我们还有一个尾节点元素，它可以帮助我们减少易于执行的操作的时间复杂性。
链表操作
链表实现必须具有以下通用方法。
getFirst：它返回第一个节点上存在的数据(如果有的话，否则抛出异常)。
它仅返回" if(this。
Size！= 0！)"提供的" this.head.data"，即，如果"链接"列表的大小不为零。getLast：返回最后一个节点上存在的数据(如果有的话，否则抛出异常)。
它仅返回" if(this。
Size！= 0！)"提供的" this.tail.data"，即，如果"链接"列表的大小不为零。getAt：它使用一个整数索引作为参数，如果索引有效(即如果index> = 0并且index <链接列表的大小)，则返回该索引处存在的元素的数据。
getNodeAt：它将一个整数索引作为参数，如果索引有效(即如果index> = 0且index <链接列表的大小)，则返回该索引处的Node。
addLast：接受链接列表类型的输入，然后将其追加到链接列表的最后一个位置，从而将大小增加" +1"，并将"尾部"指向新添加的Node。
addFirst：它接受链接列表类型的输入，然后将其追加到链接列表的第一位置，从而将大小增加" +1"，并将" head"指向新添加的Node。
addAt：它接受链表的类型的输入，并且还使用整数索引(使其等于'k')作为参数，然后将其(数据)附加在链表的第k个位置，从而将大小增加" +1"。
如果要添加的元素是" First"或者" Last"，则分别调用" addFirst"或者" addLast"。removeFirst：删除链接列表的第一个元素(假设列表不是一个空列表，其中抛出异常)，并将" head"指向第二个元素(如果有的话)，并通过' 1'。
同样，它返回删除的数据。removeLast：删除链接列表的最后一个元素(假设列表不是一个空列表，其中抛出异常)，并将" tail"移动到最后一个第二个元素(如果有的话)，并减小大小'1'。
同样，它返回删除的数据。removeAt：它以整数索引(比如说k)作为参数，并且如果索引有效(即，如果index> = 0且index <链表的大小)，则移除链表的'kth'元素(前提是链表是而不是一个空列表，它会引发异常)并将大小减小
1。
同样，它返回删除的数据。
如果要删除的元素是" First"或者" Last"，则分别调用" removeFirst"或者" removeLast"。display：此方法通过从指向" head"的指针开始直到指向" null"的指针遍历，来打印整个Linked列表。
Java中的链表实现
package com.theitroad.ds;
public class LinkedList {
private class Node {
int data;
Node next;
}
private Node head;
private Node tail;
private int size;
public int size() {
return this.size;
}
public int getFirst() throws Exception {
if (this.size == 0) {
throw new Exception("LL is Empty.");
}
return this.head.data;
}
public int getLast() throws Exception {
if (this.size == 0) {
throw new Exception("LL is Empty.");
}
return this.tail.data;
}
public int getAt(int idx) throws Exception {
if (this.size == 0) {
throw new Exception("LL is Empty.");
}
if (idx < 0 || idx >= this.size) {
throw new Exception("Invalid Index.");
}
Node temp = this.head;
for (int i = 1; i <= idx; i++) {
temp = temp.next;
}
return temp.data;
}
private Node getNodeAt(int idx) throws Exception {
if (this.size == 0) {
throw new Exception("LL is Empty.");
}
if (idx < 0 || idx >= this.size) {
throw new Exception("Invalid Index.");
}
Node temp = this.head;
for (int i = 1; i <= idx; i++) {
temp = temp.next;
}
return temp;
}
public void addLast(int item) {
//create
Node nn = new Node();
nn.data = item;
nn.next = null;
//attach
if (this.size > 0)
this.tail.next = nn;
//dm update
if (this.size == 0) {
this.head = nn;
this.tail = nn;
this.size += 1;
} else {
this.tail = nn;
this.size += 1;
}
}
public void addFirst(int item) {
//create
Node nn = new Node();
nn.data = item;
nn.next = null;
//attach
nn.next = this.head;
//dm update
if (this.size == 0) {
this.head = nn;
this.tail = nn;
this.size++;
} else {
this.head = nn;
this.size++;
}
}
public void addAt(int item, int idx) throws Exception {
if (idx < 0 || idx > this.size) {
throw new Exception("Invalid Index.");
}
if (idx == 0) {
addFirst(item);
} else if (idx == this.size) {
addLast(item);
} else {
//create
Node nn = new Node();
nn.data = item;
nn.next = null;
//attach
Node nm1 = getNodeAt(idx - 1);
Node np1 = nm1.next;
nm1.next = nn;
nn.next = np1;
//dm
this.size++;
}
}
public int removeFirst() throws Exception {
if (this.size == 0) {
throw new Exception("LL is empty.");
}
Node temp = this.head;
if (this.size == 1) {
this.head = null;
this.tail = null;
this.size = 0;
} else {
this.head = this.head.next;
this.size--;
}
return temp.data;
}
public int removeLast() throws Exception {
if (this.size == 0) {
throw new Exception("LL is empty.");
}
Node temp = this.tail;
if (this.size == 1) {
this.head = null;
this.tail = null;
this.size = 0;
} else {
Node sm2 = getNodeAt(this.size - 2);
sm2.next = null;
this.tail = sm2;
this.size--;
}
return temp.data;
}
public int removeAt(int idx) throws Exception {
if (this.size == 0) {
throw new Exception("LL is empty.");
}
if (idx < 0 || idx >= this.size) {
throw new Exception("Invalid Index.");
}
if (idx == 0) {
return removeFirst();
} else if (idx == this.size - 1) {
return removeLast();
} else {
Node nm1 = getNodeAt(idx - 1);
Node n = nm1.next;
Node np1 = n.next;
nm1.next = np1;
this.size--;
return n.data;
}
}
public void display() {
System.out.println("----------------------");
Node temp = this.head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println(".");
System.out.println("----------------------");
}
public static void main(String[] args) throws Exception {
LinkedList list = new LinkedList();
list.addLast(10);
list.addLast(20);
list.addLast(30);
list.addLast(40);
//this will display the list
list.display();
//first element i.e.10 should be printed
System.out.println(list.getFirst());
//last element i.e.40 should be printed
System.out.println(list.getLast());
//element at 3rd index i.e.40 should be printed
System.out.println(list.getAt(3));
//a memory address of a node should be printed
System.out.println(list.getNodeAt(3));
//10 should be removed and printed
System.out.println(list.removeFirst());
//40 should be removed and printed
System.out.println(list.removeLast());
//list without 10 and 40 should be printed
list.display();
//100 should be added at first
list.addFirst(100);
list.display();
//30 should be removed
list.removeAt(2);
//300 should be added at 2nd index
list.addAt(300, 2);
list.display();
}
}
注意：Java提供了LinkedList的实现。
对于实际编程，请使用官方实现。
<p><a href="https://www.theitroad.local/13386/java-linkedlist-linkedlist-java">Java LinkedList – LinkedList In Java</a></p>
链表操作时间复杂度
| Operations | Time Complexity |
|---|---|
| getFirst | O(1) |
| getLast | O(1) {注意：这是因为我们也有'tail'指针，否则应该是O（n）} |
| getAt | O(n) |
| getNodeAt | O(n) |
| addLast | O(1) {注意：这是因为我们也有'tail'指针，否则应该是O（n）} |
| addFirst | O(1) |
| addAt | O(n) |
| removeFirst | O(1) |
| removeLast | O(1) {注意：这是因为我们也有'tail'指针，否则应该是O（n）} |
| removeAt | O(n) |
| Display | O(n) |
