与数组一样，链表也是一种线性数据结构。与数组不同，链表元素不存储在相邻的位置；元素使用指针链接。
null
为什么是链表？ 数组可用于存储类似类型的线性数据，但数组有以下限制。 1) 数组的大小是固定的：所以我们必须提前知道元素数量的上限。此外，通常，无论使用情况如何，分配的内存都等于上限。 2) 在元素数组中插入新元素的成本很高，因为必须为新元素创建房间，并且要创建房间，必须移动现有元素，但在链表中，如果我们有头节点，那么我们可以通过它遍历到任何节点，并在所需位置插入新节点。 例如，在一个系统中，如果我们在一个数组id[]中维护一个已排序的id列表。 id[]=[10001010105020002040]。 如果我们想插入一个新的ID 1005，那么为了保持排序顺序，我们必须将所有元素移到1000之后（不包括1000）。 除非使用某些特殊技术，否则删除数组的代价也很高。例如，要删除id[]中的1010，必须移动1010之后的所有内容，因为要做的工作太多，这会影响代码的效率。 与阵列相比的优势 1) 动态大小 2) 易于插入/删除 缺点： 1) 不允许随机访问。我们必须从第一个节点（头节点）开始依次访问元素。因此，我们无法使用链表的默认实现高效地进行二进制搜索。读一读 在这里 . 2) 列表中的每个元素都需要为指针留出额外的内存空间。 3) 不友好。由于数组元素是连续的位置，所以存在引用的位置，而在链表的情况下不存在引用的位置。 陈述： 链表由指向链表第一个节点的指针表示。第一个节点称为头部。如果链表为空，则head的值将指向NULL。 列表中的每个节点至少由两部分组成： 1） 数据（我们可以存储整数、字符串或任何类型的数据）。 2） 指向下一个节点（将一个节点连接到另一个节点）的指针（或引用） 在C语言中，我们可以使用结构来表示节点。下面是一个包含整数数据的链表节点的示例。 在Java或C#中，LinkedList可以表示为类，节点可以表示为单独的类。LinkedList类包含节点类类型的引用。
C
// A linked list node struct Node { int data; struct Node* next; }; |
C++
class Node { public : int data; Node* next; }; |
JAVA
class LinkedList { Node head; // head of the list /* Linked list Node*/ class Node { int data; Node next; // Constructor to create a new node // Next is by default initialized // as null Node( int d) { data = d; } } } |
python
# Node class class Node: # Function to initialize the node object def __init__( self , data): self .data = data # Assign data self . next = None # Initialize # next as null # Linked List class class LinkedList: # Function to initialize the Linked # List object def __init__( self ): self .head = None |
C#
class LinkedList { // The first node(head) of the linked list // Will be an object of type Node (null by default) Node head; class Node { int data; Node next; // Constructor to create a new node Node( int d) { data = d; } } } |
Javascript
<script> var head; // head of the list /* Linked list Node*/ class Node { // Constructor to create a new node // Next is by default initialized // as null constructor(val) { this .data = val; this .next = null ; } } // This code is contributed by gauravrajput1 </script> |
C语言中的第一个简单链表 让我们创建一个包含3个节点的简单链表。
C++
// A simple CPP program to introduce // a linked list #include <bits/stdc++.h> using namespace std; class Node { public : int data; Node* next; }; // Program to create a simple linked // list with 3 nodes int main() { Node* head = NULL; Node* second = NULL; Node* third = NULL; // allocate 3 nodes in the heap head = new Node(); second = new Node(); third = new Node(); /* Three blocks have been allocated dynamically. We have pointers to these three blocks as head, 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 first block (block pointed by the head). And next pointer of the 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 the data part of the 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 the head is sufficient to represent the whole list. We can traverse the complete list by following the next pointers. */ return 0; } // This code is contributed by rathbhupendra |
C
// A simple C program to introduce // a linked list #include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node* 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 head, 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. */ return 0; } |
JAVA
// A simple Java program to introduce a linked list 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 } /* 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 head, 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 | +----+------+ +----+------+ +----+------+ */ } } |
python
# A simple Python program to introduce a linked list # Node class class Node: # Function to initialise the node object def __init__( self , data): self .data = data # Assign data self . next = None # Initialize next as null # Linked List class contains a Node object class LinkedList: # Function to initialize head def __init__( self ): self .head = None # Code execution starts here if __name__ = = '__main__' : # Start with the empty list llist = LinkedList() llist.head = Node( 1 ) second = Node( 2 ) third = Node( 3 ) ''' Three nodes have been created. We have references to these three blocks as head, second and third llist.head second third | | | | | | +----+------+ +----+------+ +----+------+ | 1 | None | | 2 | None | | 3 | None | +----+------+ +----+------+ +----+------+ ''' llist.head. next = second; # Link first node with second ''' 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 second Node refers to third. So all three nodes are linked. llist.head second third | | | | | | +----+------+ +----+------+ +----+------+ | 1 | o-------->| 2 | o-------->| 3 | null | +----+------+ +----+------+ +----+------+ ''' |
C#
// A simple C# program to introduce a linked list 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 } /* 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 head, 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 | +----+------+ +----+------+ +----+------+ */ } } // This code has been contributed by 29AjayKumar |
链表遍历 在上一个程序中，我们创建了一个包含三个节点的简单链表。让我们遍历创建的列表并打印每个节点的数据。对于遍历，让我们编写一个通用函数printList（），用于打印任何给定的列表。
我们强烈建议您在继续解决方案之前单击此处并进行练习。
C++
// A simple C++ program for traversal of a linked list #include <bits/stdc++.h> using namespace std; class Node { public : int data; Node* next; }; // This function prints contents of linked list // starting from the given node void printList(Node* n) { while (n != NULL) { cout << n->data << " " ; n = n->next; } } // Driver code int main() { Node* head = NULL; Node* second = NULL; Node* third = NULL; // allocate 3 nodes in the heap head = new Node(); second = new Node(); third = new Node(); head->data = 1; // assign data in first node head->next = second; // Link first node with second second->data = 2; // assign data to second node second->next = third; third->data = 3; // assign data to third node third->next = NULL; printList(head); return 0; } // This is code is contributed by rathbhupendra |
C
// A simple C program for traversal of a linked list #include <stdio.h> #include <stdlib.h> 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; } } 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)); head->data = 1; // assign data in first node head->next = second; // Link first node with second second->data = 2; // assign data to second node second->next = third; third->data = 3; // assign data to third node third->next = NULL; printList(head); return 0; } |
JAVA
// A simple Java program for traversal of a linked list 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) { this .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 ); llist.head.next = second; // Link first node with the second node second.next = third; // Link second node with the third node llist.printList(); } } |
Python3
# A simple Python program for traversal of a linked list # Node class class Node: # Function to initialise the node object def __init__( self , data): self .data = data # Assign data self . next = None # Initialize next as null # Linked List class contains a Node object class LinkedList: # Function to initialize head def __init__( self ): self .head = None # This function prints contents of linked list # starting from head def printList( self ): temp = self .head while (temp): print (temp.data) temp = temp. next # Code execution starts here if __name__ = = '__main__' : # Start with the empty list llist = LinkedList() llist.head = Node( 1 ) second = Node( 2 ) third = Node( 3 ) llist.head. next = second; # Link first node with second second. next = third; # Link second node with the third node llist.printList() |
C#
// A simple C# program for traversal of a linked list 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); llist.head.next = second; // Link first node with the second node second.next = third; // Link second node with the third node llist.printList(); } } /* This code contributed by PrinciRaj1992 */ |
Javascript
<script> // A simple javascript program for traversal of a linked list var head; // head of list /* Linked list Node. This inner class is made so that main() can access it */ class Node { constructor(val) { this .data = val; this .next = null ; } } /* This function prints contents of linked list starting from head */ function printList() { var n = head; while (n != null ) { document.write(n.data + " " ); n = n.next; } } /* method to create a simple linked list with 3 nodes*/ /* Start with the empty list. */ var head = new Node(1); var second = new Node(2); var third = new Node(3); head.next = second; // Link first node with the second node second.next = third; // Link second node with the third node printList(); // This code contributed by gauravrajput1 </script> |
输出：
1 2 3
重要链接： 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
