Chào ace, bài xích này chúng ta sẽ khám phá về Linked List(danh sách link đơn) trong series tự học tập về cấu trúc dữ liệu cùng giải thuật, sau đây hutgiammo.com sẽ ra mắt và chia sẻ chi tiết(khái niệm, độ phức tạp, vận dụng của nó, code ví dụ…) về nó trải qua các phần sau.

Bạn đang xem: Danh sách liên kết đơn

Giống như kiểu dữ liệu array (mảng), Linked list là một cấu tạo dữ liệu con đường tính. Tuy vậy 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ớ giáp nhau, nhưng các thành phần của linked menu sẽ được link với nhau bằng phương pháp sử dụng những con trỏ.

*
Môhìnhmộtdanhsáchliênkết

Nội dung chính


1. Vì sao lại là Linked List?

Array (mảng) hoàn toàn có thể được sử dụng để tàng trữ dữ liệu thuộc cùng một kiểu dữ liệu, một bí quyết tuyến tính. Nhưng mà array tồn tại những hạn chế sau:

1. Size của các arrays là cố gắng định: bởi vì vậy bọn họ sẽ phải biết trước số lượng giới hạn trên (upper limit) về số phần tử. Bên cạnh ra, bọn họ cũng buộc phải cấp phát số lượng ô nhớ bởi với giới hạn trên về số phần tử, bất kỳ ta có sử dụng hết số ô nhớ kia hay không.


2. Câu hỏi chèn thêm một trong những phần tử mới vào một trong những mảng tốn khá nhiều công đoạn, vì họ sẽ bắt buộc tạo chỗ chứa cho thành phần mới, với để tạo ra ra vị trí chứa đựng này thì các thành phần hiện tại trong mảng sẽ bắt buộc được di chuyển (dịch quý phái trái, hoặc dịch sang cần tùy ngôi trường hợp).

Ví dụ, trong một hệ thống, nếu chúng ta duy trì một danh sách đã được sắp tới xếp những IDs phía bên trong một mảng thương hiệu là id<>.:

id<> = <1000, 1010, 1050, 2000, 2040>.

Và nếu 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 trang bị tự đang được thu xếp của mảng, họ sẽ phải dịch rời tất cả các bộ phận nằm sau 1000 (ngoại trừ 1000) thanh lịch phải.

Việc xóa bỏ bộ phận khỏi mảng cũng rất mất công, trừ lúc sử dụng một trong những kỹ thuật đặc biệt. Ví dụ, nhằm xóa 1010 khỏi mảng id<>, thì mọi bộ phận nằm sau 1010 sẽ phải được di chuyển sang trái.


2. Ưu điểm của Linked danh sách so cùng với Array

1. Linked danh mục có form size động

2. Thuận tiện chèn thêm phần tử vào mảng, với xóa phần tử khỏi mảng.

3. Tiêu giảm của Linked List

1. Ko thể tiến hành truy cập tự dưng (random access). Bọn họ phải truy cập đến các bộ phận của Linked list một bí quyết tuần tự, bắt đầu từ node đầu tiên. Vì vậy bọn họ sẽ ko thể triển khai tìm tìm nhị phân (binary search) cùng với Linked các mục một phương pháp hiệu quả, so với dạng cài đặt mặc định của Linked List.

2. Mỗi bộ phận của Linked danh mục đều đựng một con trỏ (pointer) và cần được cấp phát bộ lưu trữ (ô nhớ) cho các con trỏ này.

3. Linked menu không gần gũi với bộ nhớ lưu trữ cache. Cũng chính vì các phần tử trong Array được bố trí nằm tức tốc kề, thường xuyên nhau, nên bạn cũng có thể dễ dàng truy cập đến các thành phần của Array thông qua các địa chỉ tham chiếu được bộc lộ bằng các chữ số, trong khi đó vấn đề này là không thể so với Linked List.

4. Tế bào tả

Một Linked các mục (danh sách liên kết) sẽ được biểu diễn vày một bé trỏ (pointer) trỏ đến node thứ nhất của Linked menu đó. Node thứ nhất của Linked danh mục được gọi là node head. Nếu như Linked danh mục là trống, giá trị của node head đang là NULL.

Mỗi node ở phía bên trong một Linked list sẽ bao gồm ít độc nhất vô nhị hai nhân tố sau:

1. Data (dữ liệu, hoàn toàn có thể là hình dáng số, kiểu ký tự, …)

2. Pointer (con trỏ) hoặc hoàn toàn có thể hiểu là reference (tham chiếu) cho tới node tiếp theo trong Linked List.

Trong ngữ điệu lập trình C, chúng ta có thể biểu diễn một node bằng phương pháp sử dụng kiểu dữ 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.

Xem thêm: Các Dạng Bài Tập Rút Gọn Căn Thức Lớp 9, Rút Gọn Biểu Thức Chứa Căn Toán 9


Trong Java hoặc C#, Linked List hoàn toàn có thể được biểu diễn dưới dạng một class với một Node có thể được biểu diễn thành một class không giống nữa. Class LinkedList chứa một reference (tham chiếu) nằm trong kiểu tài liệu class Node.

CodeC

// A linked danh mục node struct Node int data; struct Node* next; ; CodeC++

class Node public: int data; Node* next; ; CodeJava

class LinkedList Node head; // head of the các mục /* Linked danh sách Node*/ class Node int data; Node next; // Constructor to create a new node // Next is by mặc định initialized // as null Node(int d) data = d; CodePython

# Node class class Node: # Function khổng lồ initialize the node object def __init__(self, data): self.data = data # Assign data self.next = None # Initialize # next as null # Linked menu class class LinkedList: # Function khổng lồ initialize the Linked # danh sách object def __init__(self): self.head = NoneCodeC#

brightness_4class LinkedList // The first node(head) of the linked danh mục // Will be an object of type Node (null by default) Node head; class Node int data; Node next; // Constructor to lớn create a new node Node(int d) data = d; Trong ví dụ dưới đây, chúng ta sẽ tạo thành một linked list dễ dàng và đơn giản với 3 nodes:

CodeC

// A simple C program to lớn introduce // a linked list #include #include struct Node int data; struct Node* next; ; // Program to lớn create a simple linked // các mục with 3 nodes int main() 1 CodeC++

// A simple CPP program to introduce // a linked menu #include using namespace std; class Node public: int data; Node* next; ; // Program to lớn create a simple linked // danh sách with 3 nodes int main() +---+---+ +---+---+ +----+------+ // This code is contributed by rathbhupendra CodeJava


// A simple Java program to introduce a linked danh sách class LinkedList Node head; // head of các mục /* 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 lớn create a simple linked menu with 3 nodes*/ public static void main(String<> args) CodePython

# 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 danh mục llist = LinkedList() llist.head = Node(1) second = Node(2) third = Node(3) """ Three nodes have been created. We have references lớn 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 lớn 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 khổng lồ third. So all three nodes are linked. Llist.head second third | | | | | | +----+------+ +----+------+ +----+------+ | 1 | o-------->| 2 | o-------->| 3 | null | +----+------+ +----+------+ +----+------+ """CodeC#

// A simple C# program to introduce a linked các mục using System; public class LinkedList Node head; // head of các mục /* Linked danh mục 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 khổng lồ create a simple linked danh sách with 3 nodes*/ public static void Main(String<> args) null

5. Chăm sóc Linked List

Ở lấy ví dụ như trước, chúng ta đã tạo thành một linked list dễ dàng gồm 3 nodes. Tiếp theo, bọn họ sẽ chăm sóc qua linked menu này cùng in ra phần data (dữ liệu) của từng node. Để cẩn thận linked list, ta đang viết một hàm thương hiệu là printList(), hàm này sẽ in ra đa số linked list được truyền vào làm tham số cho nó. Ví dụ:

CodeC

// A simple C program for traversal of a linked menu #include #include struct Node int data; struct Node* next; ; // This function prints contents of linked danh sách 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 lớn second node second->next = third; third->data = 3; // assign data lớn third node third->next = NULL; printList(head); return 0; CodeC++

// A simple C++ program for traversal of a linked danh mục #include using namespace std; class Node public: int data; Node* next; ; // This function prints contents of linked menu // starting from the given node void printList(Node* n) while (n != NULL) cout data 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; // links first node with second second->data = 2; // assign data lớn second node second->next = third; third->data = 3; // assign data khổng lồ third node third->next = NULL; printList(head); return 0; CodeJava

// A simple Java program for traversal of a linked danh mục class LinkedList Node head; // head of list /* Linked danh mục 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 các mục starting from head */ public void printList() Node n = head; while (n != null) System.out.print(n.data + " "); n = n.next; /* method khổng lồ create a simple linked danh sách 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; // links 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 menu # Node class class Node: # Function lớn initialise the node object def __init__(self, data): self.data = data # Assign data self.next = None # Initialize next as null # Linked menu class contains a Node object class LinkedList: # Function khổng lồ initialize head def __init__(self): self.head = None # This function prints contents of linked danh mục # 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 các mục llist = LinkedList() llist.head = Node(1) second = Node(2) third = Node(3) llist.head.next = second; # links first node with second second.next = third; # liên kết second node with the third node llist.printList() CodeC#

// A simple C# program for traversal of a linked menu using System; public class LinkedList Node head; // head of menu /* Linked các mục 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 danh sách starting from head */ public void printList() Node n = head; while (n != null) Console.Write(n.data + " "); n = n.next; /* method to lớn create a simple linked các mục 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; // links second node with the third node llist.printList(); kết quả in ra là: