Chào ace, bài này tất cả chúng ta sẽ khám phá về Linked List ( danh sách liên kết đơn ) trong series tự học về cấu trúc tài liệu và giải thuật, sau đây cafedev sẽ ra mắt và san sẻ chi tiết cụ thể ( khái niệm, độ phức tạp, ứng dụng của nó, code ví dụ … ) về nó trải qua những phần sau .
Giống như kiểu dữ liệu array (mảng), Linked List là một cấu trúc dữ liệu tuyến tính. Tuy nhiên khác với array, các phần tử của linked list không được lưu trữ tại các vị trí ô nhớ liền kề nhau, mà các phần tử của linked list sẽ được liên kết với nhau bằng cách sử dụng các con trỏ.
Bạn đang đọc: [CTDL] – Danh sách liên kết đơn – Linked List – Phần 1. Giới thiệu » https://final-blade.com
Mô hình một danh sách liên kết
Tóm Tắt
1. Tại sao lại là Linked List?
Array ( mảng ) hoàn toàn có thể được sử dụng để tàng trữ tài liệu thuộc cùng một kiểu tài liệu, một cách tuyến tính. Nhưng array sống sót những hạn chế sau :
1. Kích thước của những arrays là cố định và thắt chặt : Vì vậy tất cả chúng ta sẽ phải biết trước số lượng giới hạn trên ( upper limit ) về số thành phần. Ngoài ra, tất cả chúng ta cũng phải cấp phép số lượng ô nhớ bằng với số lượng giới hạn trên về số thành phần, bất kể ta có sử dụng hết số ô nhớ đó hay không .
2. Việc chèn thêm một thành phần mới vào một mảng tốn khá nhiều quy trình, vì tất cả chúng ta sẽ phải tạo chỗ chứa cho thành phần mới, và để tạo ra chỗ chứa này thì những thành phần hiện tại trong mảng sẽ phải được di dời ( dịch sang trái, hoặc dịch sang phải tùy trường hợp ) .
Ví dụ, trong một mạng lưới hệ thống, nếu tất cả chúng ta duy trì một danh sách đã được sắp xếp những IDs bên trong một mảng tên là id [ ]. :
id [ ] = [ 1000, 1010, 1050, 2000, 2040 ] .
Và nếu tất cả chúng ta muốn chèn thêm một ID là 1005 vào mảng id [ ], vậy thì, để duy trì được thứ tự đã được sắp xếp của mảng, tất cả chúng ta sẽ phải di dời toàn bộ những thành phần nằm sau 1000 ( ngoại trừ 1000 ) sang phải .
Việc xóa bỏ thành phần khỏi mảng cũng khá mất công, trừ khi sử dụng 1 số ít kỹ thuật đặc biệt quan trọng. Ví dụ, để xóa 1010 khỏi mảng id [ ], thì mọi thành phần nằm sau 1010 sẽ phải được di dời sang trái .
2. Ưu điểm của Linked List so với Array
1. Linked List có kích cỡ động
2. Dễ dàng chèn thêm thành phần vào mảng, và xóa thành phần khỏi mảng .
3. Hạn chế của Linked List
1. Không thể thực thi truy vấn ngẫu nhiên ( random access ). Chúng ta phải truy vấn đến những thành phần của Linked List một cách tuần tự, mở màn từ node tiên phong. Vì vậy tất cả chúng ta sẽ không hề thực thi tìm kiếm nhị phân ( binary search ) với Linked List một cách hiệu suất cao, so với dạng thiết lập mặc định của Linked List .
2. Mỗi thành phần của Linked List đều chứa một con trỏ ( pointer ) và cần phải cấp phép bộ nhớ ( ô nhớ ) cho những con trỏ này .
3. Linked List không thân thiện với bộ nhớ cache. Bởi vì những thành phần trong Array được sắp xếp nằm liền kề, liên tục nhau, nên tất cả chúng ta hoàn toàn có thể thuận tiện truy vấn đến những thành phần của Array trải qua những vị trí tham chiếu được bộc lộ bằng những chữ số, trong khi đó điều này là không hề so với Linked List .
4. Mô tả
Một Linked List ( danh sách liên kết ) sẽ được màn biểu diễn bởi một con trỏ ( pointer ) trỏ đến node tiên phong của Linked List đó. Node tiên phong của Linked List được gọi là node head. Nếu Linked List là trống, giá trị của node head sẽ là NULL .
Mỗi node ở bên trong một Linked List sẽ gồm có tối thiểu hai thành phần sau :
1. data ( tài liệu, hoàn toàn có thể là kiểu số, kiểu ký tự, … )
2. pointer ( con trỏ ) hoặc hoàn toàn có thể hiểu là reference ( tham chiếu ) tới node tiếp theo trong Linked List .
Trong ngôn từ lập trình C, tất cả chúng ta hoàn toàn có thể màn biểu diễn một node bằng cách sử dụng kiểu tài liệu struct. Dưới đây là ví dụ về một node có kiểu tài liệu integer của một Linked List .
Trong Java hoặc C #, Linked List hoàn toàn có thể được màn biểu diễn dưới dạng một class và một Node hoàn toàn có thể được màn biểu diễn thành một class khác nữa. class LinkedList chứa một reference ( tham chiếu ) thuộc kiểu tài liệu class Node .
Code C
// A linked list node
struct Node {
int data;
struct Node* next;
};
Code C++
class Node {
public:
int data;
Node* next;
}; Code 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; }
}
}
Code 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
Code C#
brightness_4
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; }
}
}
Trong ví dụ dưới đây, tất cả chúng ta sẽ tạo ra một linked list đơn thuần với 3 nodes :
Code C
// A simple C program to introduce
// a linked list
#include
#include
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;
}
Code C++
// A simple CPP program to introduce
// a linked list
#include
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
Code 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 |
+----+------+ +----+------+ +----+------+ */
}
}
Code 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 |
+----+------+ +----+------+ +----+------+
'''Code 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 |
+----+------+ +----+------+ +----+------+ */
}
} 5. Duyệt Linked List
Ở ví dụ trước, tất cả chúng ta đã tạo ra một linked list đơn thuần gồm 3 nodes. Tiếp theo, tất cả chúng ta sẽ duyệt qua linked list này và in ra phần data ( tài liệu ) của từng node. Để duyệt linked list, ta sẽ viết một hàm tên là printList ( ), hàm này sẽ in ra mọi linked list được truyền vào làm tham số cho nó. Ví dụ :
Code C
// A simple C program for traversal of a linked list
#include
#include
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;
}
Code C++
// A simple C++ program for traversal of a linked list
#include
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;
} Code 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)
{
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();
}
}
Python 3
# 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()
Code 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();
}
} Kết quả in ra là :
1 2 3
Nguồn và Tài liệu tiếng anh tham khảo:
Tài liệu từ cafedev:
Nếu bạn thấy hay và hữu dụng, bạn hoàn toàn có thể tham gia những kênh sau của cafedev để nhận được nhiều hơn nữa :
Chào thân ái và quyết thắng !
Đăng ký kênh youtube để ủng hộ Cafedev nha các bạn, Thanks you!
Source: https://final-blade.com
Category: Kiến thức Internet
