基础知识
介绍：链表与数组一样，同属于线性表的一个子集。不同之处在于链表元素并不需要存储到一块连续的内存空间；
链表中的元素通过指针来链接并维护各个节点之间的联系，可使用连续的内存空间、亦可不使用连续的内存空间。
使用链表的原因：
1、数组类型长度是固定的，一旦申明不可以修改长度。在实际使用中我们必须事先知道元素数量的上限。
2、实际使用过程中分配的数组上限的内存空间，而事实不一定占用那么多空间。
3、插入删除成本高，必须要进行位移。插入平均位移n/2个元素，删除移动(n-1)/2个元素。最理想的时间成本
O(1)即被删除/插入元素后面没有元素。
链表有点：
1、动态分配内存，即用即申请，占用空间大小也是动态的。
2、插入、删除方便，特别是在头和尾，修改指针地址即可。
缺点：
1、不可以随机访问，必须遍历。二分查找时间复杂度为O(n),数组二分查找时间复杂度O(log2n) （注：O(n)> O(log2n)）
2、列表中每个节点还需要额外的内存空间存储指针域（链）数据
3、数组中元素占用的存储空间是连续的，可以根据索引进行访问元素,链表不支持此操作。
数据展现：
链表第一个节点叫头节点。如果链表为空，数据域、指针域(链、引用)都是NULL
c语言中通常用结构展示数据，在java或者C#中用类和另外一个节点类(Node)来表示，LinkedList类包含Node类型的引用。
创建3个节点并遍历
c语言:
// A simple C program to introduce
// a linked list
#include <stdio.h>
#include <stdlib.h>
// A linked list node
struct Node {
int data;
struct Node* next;
};
// This function prints contents of linked list starting from
// the given node
void printList(struct Node* n)
{
while (n != NULL) {
printf(" %d ", n->data);
n = n->next;
}
}
// Program to create a simple linked
// list with 3 nodes
int main()
{
struct Node* head = NULL;
struct Node* second = NULL;
struct Node* third = NULL;
// allocate 3 nodes in the heap
head = (struct Node*)malloc(sizeof(struct Node));
second = (struct Node*)malloc(sizeof(struct Node));
third = (struct Node*)malloc(sizeof(struct Node));
/* Three blocks have been allocated dynamically.
We have pointers to these three blocks as first,
second and third
head second third
| | |
| | |
+---+-----+ +----+----+ +----+----+
| # | # | | # | # | | # | # |
+---+-----+ +----+----+ +----+----+
# represents any random value.
Data is random because we haven’t assigned
anything yet */
head->data = 1; // assign data in first node
head->next = second; // Link first node with
// the second node
/* data has been assigned to the data part of the first
block (block pointed by the head). And next
pointer of first block points to second.
So they both are linked.
head second third
| | |
| | |
+---+---+ +----+----+ +-----+----+
| 1 | o----->| # | # | | # | # |
+---+---+ +----+----+ +-----+----+
*/
// assign data to second node
second->data = 2;
// Link second node with the third node
second->next = third;
/* data has been assigned to the data part of the second
block (block pointed by second). And next
pointer of the second block points to the third
block. So all three blocks are linked.
head second third
| | |
| | |
+---+---+ +---+---+ +----+----+
| 1 | o----->| 2 | o-----> | # | # |
+---+---+ +---+---+ +----+----+ */
third->data = 3; // assign data to third node
third->next = NULL;
/* data has been assigned to data part of third
block (block pointed by third). And next pointer
of the third block is made NULL to indicate
that the linked list is terminated here.
We have the linked list ready.
head
|
|
+---+---+ +---+---+ +----+------+
| 1 | o----->| 2 | o-----> | 3 | NULL |
+---+---+ +---+---+ +----+------+
Note that only head is sufficient to represent
the whole list. We can traverse the complete
list by following next pointers. */
printList(head);
return 0;
}
输出结果：
1 2 3
java:
// A simple Java program to introduce a linked list
public class LinkedList {
Node head; // head of list
/* Linked list Node. This inner class is made static so that
main() can access it */
static class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
} // Constructor
}
/* This function prints contents of linked list starting from head */
public void printList()
{
Node n = head;
while (n != null) {
System.out.print(n.data + " ");
n = n.next;
}
}
/* method to create a simple linked list with 3 nodes*/
public static void main(String[] args)
{
/* Start with the empty list. */
LinkedList llist = new LinkedList();
llist.head = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
/* Three nodes have been allocated dynamically.
We have references to these three blocks as first,
second and third
llist.head second third
| | |
| | |
+----+------+ +----+------+ +----+------+
| 1 | null | | 2 | null | | 3 | null |
+----+------+ +----+------+ +----+------+ */
llist.head.next = second; // Link first node with the second node
/* Now next of the first Node refers to the second. So they
both are linked.
llist.head second third
| | |
| | |
+----+------+ +----+------+ +----+------+
| 1 | o-------->| 2 | null | | 3 | null |
+----+------+ +----+------+ +----+------+ */
second.next = third; // Link second node with the third node
/* Now next of the second Node refers to third. So all three
nodes are linked.
llist.head second third
| | |
| | |
+----+------+ +----+------+ +----+------+
| 1 | o-------->| 2 | o-------->| 3 | null |
+----+------+ +----+------+ +----+------+ */
llist.printList();
}
}
c#
using System;
public class LinkedList {
Node head; // head of list
/* Linked list Node. This inner class is made static so that
main() can access it */
public class Node {
public int data;
public Node next;
public Node(int d)
{
data = d;
next = null;
} // Constructor
}
/* This function prints contents of
linked list starting from head */
public void printList()
{
Node n = head;
while (n != null) {
Console.Write(n.data + " ");
n = n.next;
}
}
/* method to create a simple linked list with 3 nodes*/
public static void Main(String[] args)
{
/* Start with the empty list. */
LinkedList llist = new LinkedList();
llist.head = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
/* Three nodes have been allocated dynamically.
We have references to these three blocks as first,
second and third
llist.head second third
| | |
| | |
+----+------+ +----+------+ +----+------+
| 1 | null | | 2 | null | | 3 | null |
+----+------+ +----+------+ +----+------+ */
llist.head.next = second; // Link first node with the second node
/* Now next of first Node refers to second. So they
both are linked.
llist.head second third
| | |
| | |
+----+------+ +----+------+ +----+------+
| 1 | o-------->| 2 | null | | 3 | null |
+----+------+ +----+------+ +----+------+ */
second.next = third; // Link second node with the third node
/* Now next of the second Node refers to third. So all three
nodes are linked.
llist.head second third
| | |
| | |
+----+------+ +----+------+ +----+------+
| 1 | o-------->| 2 | o--------> | 3 | null |
+----+------+ +----+------+ +----+------+ */
llist.printList();
}
}
来源：https://www.geeksforgeeks.org/linked-list-set-1-introduction/