[CTDL] Danh Sách Liên Kết đơn - Linked List - Phần 2. Chèn Thêm Node

🔥CHỌN LỌC TOP NHỮNG KHOÁ HỌC LẬP TRÌNH ONLINE NHIỀU NGƯỜI THEO HOC TẠI ĐÂY🔥

Chào ace, bài này chúng ta sẽ tìm hiểu về cách thêm Node trong Linked List(danh sách liên kết đơn) trong series tự học về cấu trúc dữ liệu và giải thuật, sau đây cafedev sẽ giới thiệu và chia sẻ chi tiết(khái niệm, độ phức tạp, ứng dụng của nó, code ví dụ…) về nó thông qua các phần sau.

Trong bài trước, chúng ta đã tìm hiểu tổng quan về danh sách liên kết đơn – Linked List. Chúng ta cũng đã tạo ra một danh sách liên kết đơn đơn giản gồm 3 nodes và thực hiện duyệt danh sách liên kết đơn.

Tất cả các đoạn chương trình được thảo luận trong bài học này đều sẽ sử dụng danh sách liên kết đơn – linked list để mô tả.

Code C

// A linked list node struct Node { int data; struct Node *next; };

Code C++

// A linked list node class Node { public: int data; Node *next; };

Code Java

// Linked List Class class LinkedList { Node head; // head of list /* Node Class */ class Node { int data; Node next; // Constructor to create a new node Node(int d) {data = d; next = null; } } }

Code python 3

# 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#

/* Linked list Node*/ public class Node { public int data; public Node next; public Node(int d) {data = d; next = null; } }

Trong bài học này, chúng ta sẽ tìm hiểu về các phương thức dùng để chèn thêm một node mới vào trong linked list. Một node mới có thể được chèn vào linked list theo một trong ba cách sau:

1. Chèn vào phần đầu của linked list

2. Chèn vào sau một node cụ thể nào đó

3. Chèn vào cuối linked list

1. Chèn thêm node mới vào phần đầu của linked list (gồm 4 bước)

Node mới sẽ luôn luôn được chèn vào phía trước node head của linked list được cho. Và node vừa mới được chèn thêm vào sẽ trở thành node head mới của linked list. Ví dụ, nếu linked list được cho là 10 -> 15 -> 20 -> 25 và chúng ta chèn thêm một phần tử 5 vào trước, thì linked list này sẽ trở thành 5 -> 10 -> 15 -> 20 -> 25. Chúng ta hãy gọi hàm thực hiện việc chèn thêm node mới vào đầu linked list là hàm push(). Hàm push() phải nhận vào một con trỏ trỏ đến con trỏ head, bởi vì hàm push() phải tiến hành thay đổi con trỏ head để nó trỏ đến node mới. Hình dưới đây sẽ minh họa điều này:

Sau đây là 4 bước để chèn thêm node mới vào đầu linked list:

Truyền vào cho hàm push() một tham chiếu (con trỏ trỏ đến con trỏ) tới node head của linked list, và một giá trị kiểu int mà node mới sẽ chứa giá trị đó.

1. Cấp phát bộ nhớ cho node mới

2. Truyền giá trị vào cho node mới

3. Làm cho node tiếp theo của node mới trở thành node head (tức là làm cho con trỏ next của node mới trỏ đến node head)

4. Làm cho node head trỏ đến node mới

Code ví dụ các step trên:

C

/* Given a reference (pointer to pointer) to the head of a list and an int, inserts a new node on the front of the list. */ void push(struct Node** head_ref, int new_data) { /* 1. allocate node */ struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); /* 2. put in the data */ new_node->data = new_data; /* 3. Make next of new node as head */ new_node->next = (*head_ref); /* 4. move the head to point to the new node */ (*head_ref) = new_node; }

C++

/* Given a reference (pointer to pointer) to the head of a list and an int, inserts a new node on the front of the list. */ void push(Node** head_ref, int new_data) { /* 1. allocate node */ Node* new_node = new Node(); /* 2. put in the data */ new_node->data = new_data; /* 3. Make next of new node as head */ new_node->next = (*head_ref); /* 4. move the head to point to the new node */ (*head_ref) = new_node; }

Java

/* This function is in LinkedList class. Inserts a new Node at front of the list. This method is defined inside LinkedList class shown above */ public void push(int new_data) { /* 1 & 2: Allocate the Node & Put in the data*/ Node new_node = new Node(new_data); /* 3. Make next of new Node as head */ new_node.next = head; /* 4. Move the head to point to new Node */ head = new_node; }

Python

# This function is in LinkedList class # Function to insert a new node at the beginning def push(self, new_data): # 1 & 2: Allocate the Node & # Put in the data new_node = Node(new_data) # 3. Make next of new Node as head new_node.next = self.head # 4. Move the head to point to new Node self.head = new_node

C#

/* Inserts a new Node at front of the list. */ public void push(int new_data) { /* 1 & 2: Allocate the Node & Put in the data*/ Node new_node = new Node(new_data); /* 3. Make next of new Node as head */ new_node.next = head; /* 4. Move the head to point to new Node */ head = new_node; }

Độ phức tạp thuật toán của hàm push() là O(1) bởi vì nó thực hiện một khối lượng công việc không đổi.

2. Chèn thêm node mới vào sau một node cụ thể (gồm 5 bước)

Chúng ta được cho trước một con trỏ trỏ đến một node cụ thể trong linked list, và node mới sẽ được chèn thêm vào sau node được cho trước đó.

Sau đây là 5 bước để chèn thêm node mới vào sau một node cụ thể nào đó:

Truyền vào cho hàm insertAfter() một tham chiếu trỏ đến node trước đó), và một giá trị kiểu int mà node mới sẽ chứa giá trị đó.

1. Kiểm tra xem tham chiếu trỏ đến node trước đó là prev_node có NULL hay không? Nếu NULL, chúng ta sẽ return luôn.

2. Cấp phát bộ nhớ cho node mới

3. Truyền dữ liệu vào node mới

4. Làm cho con trỏ next của node mới bằng với con trỏ next của node trước đó

5. Làm cho con trỏ next của node trước đó (prev_node) trỏ đến node mới (new_node)

Code ví dụ các bước trên:

C

/* Given a node prev_node, insert a new node after the given prev_node */ void insertAfter(struct Node* prev_node, int new_data) { /*1. check if the given prev_node is NULL */ if (prev_node == NULL) { printf("the given previous node cannot be NULL"); return; } /* 2. allocate new node */ struct Node* new_node =(struct Node*) malloc(sizeof(struct Node)); /* 3. put in the data */ new_node->data = new_data; /* 4. Make next of new node as next of prev_node */ new_node->next = prev_node->next; /* 5. move the next of prev_node as new_node */ prev_node->next = new_node; }

C++

// Given a node prev_node, insert a // new node after the given // prev_node void insertAfter(Node* prev_node, int new_data) { // 1. Check if the given prev_node is NULL if (prev_node == NULL) { cout << "the given previous node cannot be NULL"; return; } // 2. Allocate new node Node* new_node = new Node(); // 3. Put in the data new_node->data = new_data; // 4. Make next of new node as // next of prev_node new_node->next = prev_node->next; // 5. move the next of prev_node // as new_node prev_node->next = new_node; }

Java

/* This function is in LinkedList class. Inserts a new node after the given prev_node. This method is defined inside LinkedList class shown above */ public void insertAfter(Node prev_node, int new_data) { /* 1. Check if the given Node is null */ if (prev_node == null) { System.out.println("The given previous node cannot be null"); return; } /* 2. Allocate the Node & 3. Put in the data*/ Node new_node = new Node(new_data); /* 4. Make next of new Node as next of prev_node */ new_node.next = prev_node.next; /* 5. make next of prev_node as new_node */ prev_node.next = new_node; }

Python 3

# This function is in LinkedList class. # Inserts a new node after the given prev_node. This method is # defined inside LinkedList class shown above */ def insertAfter(self, prev_node, new_data): # 1. check if the given prev_node exists if prev_node is None: print "The given previous node must inLinkedList." return # 2. Create new node & # 3. Put in the data new_node = Node(new_data) # 4. Make next of new Node as next of prev_node new_node.next = prev_node.next # 5. make next of prev_node as new_node prev_node.next = new_node

C#

/* Inserts a new node after the given prev_node. */ public void insertAfter(Node prev_node, int new_data) { /* 1. Check if the given Node is null */ if (prev_node == null) { Console.WriteLine("The given previous node" + " cannot be null"); return; } /* 2 & 3: Allocate the Node & Put in the data*/ Node new_node = new Node(new_data); /* 4. Make next of new Node as next of prev_node */ new_node.next = prev_node.next; /* 5. make next of prev_node as new_node */ prev_node.next = new_node; }

Độ phức tạp thuật toán của hàm insertAfter() là O(1) bởi vì nó thực hiện một khối lượng công việc không đổi.

3. Chèn thêm node mới vào cuối linked-list

Trong trường hợp này, node mới sẽ luôn luôn được chèn thêm vào phía sau node cuối cùng của linked list. Ví dụ, nếu linked list được cho có dạng 5 -> 10 -> 15 -> 20 -> 25 và chúng ta chèn thêm một node 30 vào cuối, vậy thì linked list lúc này sẽ trở thành 5 -> 10 -> 15 -> 20 -> 25 -> 30.

Bởi vì linked list thường được biểu diễn/đại diện bởi con trỏ head của nó, nên chúng ta sẽ phải duyệt từ đầu cho tới cuối linked list và sau đó làm cho con trỏ next của node cuối cùng trỏ đến node mới được chèn vào

Dưới đây là 6 bước để chèn thêm node mới vào cuối linked list:

Truyền vào cho hàm append() một tham chiếu (con trỏ trỏ tới con trỏ) tới node head của linked list và một giá trị kiểu int mà node mới sẽ chứa giá trị đó, hàm append() sẽ thực hiện chèn một node mới vào cuối linked list

1. Cấp phát bộ nhớ cho node mới

2. Truyền dữ liệu vào node mới

3. Node mới được chèn vào sẽ trở thành node cuối cùng của linked list, vậy nên ta hãy làm cho con trỏ next của node mới này trở thành NULL

4. Nếu linked list vẫn còn trống (không chứa node nào), vậy thì hãy làm cho node mới được chèn vào trở thành node head của linked list

5. Nếu linked list không trống, vậy thì ta sẽ duyệt tới node cuối cùng của linked list

6. Làm cho con trỏ next của node cuối cùng của linked list trỏ đến node mới (new_node)

Code ví dụ các bước trên

C

/* Given a reference (pointer to pointer) to the head of a list and an int, appends a new node at the end */ void append(struct Node** head_ref, int new_data) { /* 1. allocate node */ struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); struct Node *last = *head_ref; /* used in step 5*/ /* 2. put in the data */ new_node->data = new_data; /* 3. This new node is going to be the last node, so make next of it as NULL*/ new_node->next = NULL; /* 4. If the Linked List is empty, then make the new node as head */ if (*head_ref == NULL) { *head_ref = new_node; return; } /* 5. Else traverse till the last node */ while (last->next != NULL) last = last->next; /* 6. Change the next of last node */ last->next = new_node; return; }

C++

// Given a reference (pointer to pointer) to the head // of a list and an int, appends a new node at the end void append(Node** head_ref, int new_data) { // 1. allocate node Node* new_node = new Node(); // Used in step 5 Node *last = *head_ref; // 2. Put in the data new_node->data = new_data; // 3. This new node is going to be // the last node, so make next of // it as NULL new_node->next = NULL; // 4. If the Linked List is empty, // then make the new node as head if (*head_ref == NULL) { *head_ref = new_node; return; } // 5. Else traverse till the last node while (last->next != NULL) last = last->next; // 6. Change the next of last node last->next = new_node; return; }

Java

/* Appends a new node at the end. This method is defined inside LinkedList class shown above */ public void append(int new_data) { /* 1. Allocate the Node & 2. Put in the data 3. Set next as null */ Node new_node = new Node(new_data); /* 4. If the Linked List is empty, then make the new node as head */ if (head == null) { head = new Node(new_data); return; } /* 4. This new node is going to be the last node, so make next of it as null */ new_node.next = null; /* 5. Else traverse till the last node */ Node last = head; while (last.next != null) last = last.next; /* 6. Change the next of last node */ last.next = new_node; return; }

Python

# This function is defined in Linked List class # Appends a new node at the end. This method is # defined inside LinkedList class shown above */ def append(self, new_data): # 1. Create a new node # 2. Put in the data # 3. Set next as None new_node = Node(new_data) # 4. If the Linked List is empty, then make the # new node as head if self.head is None: self.head = new_node return # 5. Else traverse till the last node last = self.head while (last.next): last = last.next # 6. Change the next of last node last.next = new_node

C#

/* Appends a new node at the end. This method is defined inside LinkedList class shown above */ public void append(int new_data) { /* 1. Allocate the Node & 2. Put in the data 3. Set next as null */ Node new_node = new Node(new_data); /* 4. If the Linked List is empty, then make the new node as head */ if (head == null) { head = new Node(new_data); return; } /* 4. This new node is going to be the last node, so make next of it as null */ new_node.next = null; /* 5. Else traverse till the last node */ Node last = head; while (last.next != null) last = last.next; /* 6. Change the next of last node */ last.next = new_node; return; }

Độ phức tạp thuật toán của hàm append() là O(n) trong đó n là số lượng nodes có trong linked list. Bởi vì chúng ta sẽ sử dụng một vòng lặp từ node head cho đến node cuối cùng của linked list, cho nên hàm append() sẽ thực hiện O(n) công việc.

Hàm này có thể được tối ưu lại để làm việc với độ phức tạp O(1) bằng cách sử dụng thêm một con trỏ nữa để trỏ đến phần đuôi (tail) của linked list.

Dưới đây là các đoạn chương trình hoàn chỉnh được viết bằng nhiều ngôn ngữ lập trình khác nhau, sử dụng tất cả các phương thức/hàm đã nêu ở trên để tạo ra một linked list.

C

// A complete working C program to demonstrate all insertion methods // on Linked List #include <stdio.h> #include <stdlib.h> // A linked list node struct Node { int data; struct Node *next; }; /* Given a reference (pointer to pointer) to the head of a list and an int, inserts a new node on the front of the list. */ void push(struct Node** head_ref, int new_data) { /* 1. allocate node */ struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); /* 2. put in the data */ new_node->data = new_data; /* 3. Make next of new node as head */ new_node->next = (*head_ref); /* 4. move the head to point to the new node */ (*head_ref) = new_node; } /* Given a node prev_node, insert a new node after the given prev_node */ void insertAfter(struct Node* prev_node, int new_data) { /*1. check if the given prev_node is NULL */ if (prev_node == NULL) { printf("the given previous node cannot be NULL"); return; } /* 2. allocate new node */ struct Node* new_node =(struct Node*) malloc(sizeof(struct Node)); /* 3. put in the data */ new_node->data = new_data; /* 4. Make next of new node as next of prev_node */ new_node->next = prev_node->next; /* 5. move the next of prev_node as new_node */ prev_node->next = new_node; } /* Given a reference (pointer to pointer) to the head of a list and an int, appends a new node at the end */ void append(struct Node** head_ref, int new_data) { /* 1. allocate node */ struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); struct Node *last = *head_ref; /* used in step 5*/ /* 2. put in the data */ new_node->data = new_data; /* 3. This new node is going to be the last node, so make next of it as NULL*/ new_node->next = NULL; /* 4. If the Linked List is empty, then make the new node as head */ if (*head_ref == NULL) { *head_ref = new_node; return; } /* 5. Else traverse till the last node */ while (last->next != NULL) last = last->next; /* 6. Change the next of last node */ last->next = new_node; return; } // This function prints contents of linked list starting from head void printList(struct Node *node) { while (node != NULL) { printf(" %d ", node->data); node = node->next; } } /* Driver program to test above functions*/ int main() { /* Start with the empty list */ struct Node* head = NULL; // Insert 6. So linked list becomes 6->NULL append(&head, 6); // Insert 7 at the beginning. So linked list becomes 7->6->NULL push(&head, 7); // Insert 1 at the beginning. So linked list becomes 1->7->6->NULL push(&head, 1); // Insert 4 at the end. So linked list becomes 1->7->6->4->NULL append(&head, 4); // Insert 8, after 7. So linked list becomes 1->7->8->6->4->NULL insertAfter(head->next, 8); printf("\n Created Linked list is: "); printList(head); return 0; }

C++

// A complete working C++ program to demonstrate // all insertion methods on Linked List #include <bits/stdc++.h> using namespace std; // A linked list node class Node { public: int data; Node *next; }; /* Given a reference (pointer to pointer) to the head of a list and an int, inserts a new node on the front of the list. */ void push(Node** head_ref, int new_data) { /* 1. allocate node */ Node* new_node = new Node(); /* 2. put in the data */ new_node->data = new_data; /* 3. Make next of new node as head */ new_node->next = (*head_ref); /* 4. move the head to point to the new node */ (*head_ref) = new_node; } /* Given a node prev_node, insert a new node after the given prev_node */ void insertAfter(Node* prev_node, int new_data) { /*1. check if the given prev_node is NULL */ if (prev_node == NULL) { cout<<"the given previous node cannot be NULL"; return; } /* 2. allocate new node */ Node* new_node = new Node(); /* 3. put in the data */ new_node->data = new_data; /* 4. Make next of new node as next of prev_node */ new_node->next = prev_node->next; /* 5. move the next of prev_node as new_node */ prev_node->next = new_node; } /* Given a reference (pointer to pointer) to the head of a list and an int, appends a new node at the end */ void append(Node** head_ref, int new_data) { /* 1. allocate node */ Node* new_node = new Node(); Node *last = *head_ref; /* used in step 5*/ /* 2. put in the data */ new_node->data = new_data; /* 3. This new node is going to be the last node, so make next of it as NULL*/ new_node->next = NULL; /* 4. If the Linked List is empty, then make the new node as head */ if (*head_ref == NULL) { *head_ref = new_node; return; } /* 5. Else traverse till the last node */ while (last->next != NULL) last = last->next; /* 6. Change the next of last node */ last->next = new_node; return; } // This function prints contents of // linked list starting from head void printList(Node *node) { while (node != NULL) { cout<<" "<<node->data; node = node->next; } } /* Driver code*/ int main() { /* Start with the empty list */ Node* head = NULL; // Insert 6. So linked list becomes 6->NULL append(&head, 6); // Insert 7 at the beginning. // So linked list becomes 7->6->NULL push(&head, 7); // Insert 1 at the beginning. // So linked list becomes 1->7->6->NULL push(&head, 1); // Insert 4 at the end. So // linked list becomes 1->7->6->4->NULL append(&head, 4); // Insert 8, after 7. So linked // list becomes 1->7->8->6->4->NULL insertAfter(head->next, 8); cout<<"Created Linked list is: "; printList(head); return 0; }

Java

// A complete working Java program to demonstrate all insertion methods // on linked list class LinkedList { Node head; // head of list /* Linked list Node*/ class Node { int data; Node next; Node(int d) {data = d; next = null; } } /* Inserts a new Node at front of the list. */ public void push(int new_data) { /* 1 & 2: Allocate the Node & Put in the data*/ Node new_node = new Node(new_data); /* 3. Make next of new Node as head */ new_node.next = head; /* 4. Move the head to point to new Node */ head = new_node; } /* Inserts a new node after the given prev_node. */ public void insertAfter(Node prev_node, int new_data) { /* 1. Check if the given Node is null */ if (prev_node == null) { System.out.println("The given previous node cannot be null"); return; } /* 2 & 3: Allocate the Node & Put in the data*/ Node new_node = new Node(new_data); /* 4. Make next of new Node as next of prev_node */ new_node.next = prev_node.next; /* 5. make next of prev_node as new_node */ prev_node.next = new_node; } /* Appends a new node at the end. This method is defined inside LinkedList class shown above */ public void append(int new_data) { /* 1. Allocate the Node & 2. Put in the data 3. Set next as null */ Node new_node = new Node(new_data); /* 4. If the Linked List is empty, then make the new node as head */ if (head == null) { head = new Node(new_data); return; } /* 4. This new node is going to be the last node, so make next of it as null */ new_node.next = null; /* 5. Else traverse till the last node */ Node last = head; while (last.next != null) last = last.next; /* 6. Change the next of last node */ last.next = new_node; return; } /* This function prints contents of linked list starting from the given node */ public void printList() { Node tnode = head; while (tnode != null) { System.out.print(tnode.data+" "); tnode = tnode.next; } } /* Driver program to test above functions. Ideally this function should be in a separate user class. It is kept here to keep code compact */ public static void main(String[] args) { /* Start with the empty list */ LinkedList llist = new LinkedList(); // Insert 6. So linked list becomes 6->NUllist llist.append(6); // Insert 7 at the beginning. So linked list becomes // 7->6->NUllist llist.push(7); // Insert 1 at the beginning. So linked list becomes // 1->7->6->NUllist llist.push(1); // Insert 4 at the end. So linked list becomes // 1->7->6->4->NUllist llist.append(4); // Insert 8, after 7. So linked list becomes // 1->7->8->6->4->NUllist llist.insertAfter(llist.head.next, 8); System.out.println("\nCreated Linked list is: "); llist.printList(); } }

Python 3

# A complete working Python program to demonstrate all # insertion methods of 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 # Functio to insert a new node at the beginning def push(self, new_data): # 1 & 2: Allocate the Node & # Put in the data new_node = Node(new_data) # 3. Make next of new Node as head new_node.next = self.head # 4. Move the head to point to new Node self.head = new_node # This function is in LinkedList class. Inserts a # new node after the given prev_node. This method is # defined inside LinkedList class shown above */ def insertAfter(self, prev_node, new_data): # 1. check if the given prev_node exists if prev_node is None: print "The given previous node must inLinkedList." return # 2. create new node & # Put in the data new_node = Node(new_data) # 4. Make next of new Node as next of prev_node new_node.next = prev_node.next # 5. make next of prev_node as new_node prev_node.next = new_node # This function is defined in Linked List class # Appends a new node at the end. This method is # defined inside LinkedList class shown above */ def append(self, new_data): # 1. Create a new node # 2. Put in the data # 3. Set next as None new_node = Node(new_data) # 4. If the Linked List is empty, then make the # new node as head if self.head is None: self.head = new_node return # 5. Else traverse till the last node last = self.head while (last.next): last = last.next # 6. Change the next of last node last.next = new_node # Utility function to print the linked list 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() # Insert 6. So linked list becomes 6->None llist.append(6) # Insert 7 at the beginning. So linked list becomes 7->6->None llist.push(7); # Insert 1 at the beginning. So linked list becomes 1->7->6->None llist.push(1); # Insert 4 at the end. So linked list becomes 1->7->6->4->None llist.append(4) # Insert 8, after 7. So linked list becomes 1 -> 7-> 8-> 6-> 4-> None llist.insertAfter(llist.head.next, 8) print 'Created linked list is:', llist.printList()

C#

// A complete working C# program to demonstrate // all insertion methods on linked list using System; class GFG { public Node head; // head of list /* Linked list Node*/ public class Node { public int data; public Node next; public Node(int d) {data = d; next = null;} } /* Inserts a new Node at front of the list. */ public void push(int new_data) { /* 1 & 2: Allocate the Node & Put in the data*/ Node new_node = new Node(new_data); /* 3. Make next of new Node as head */ new_node.next = head; /* 4. Move the head to point to new Node */ head = new_node; } /* Inserts a new node after the given prev_node. */ public void insertAfter(Node prev_node, int new_data) { /* 1. Check if the given Node is null */ if (prev_node == null) { Console.WriteLine("The given previous" + " node cannot be null"); return; } /* 2 & 3: Allocate the Node & Put in the data*/ Node new_node = new Node(new_data); /* 4. Make next of new Node as next of prev_node */ new_node.next = prev_node.next; /* 5. make next of prev_node as new_node */ prev_node.next = new_node; } /* Appends a new node at the end. This method is defined inside LinkedList class shown above */ public void append(int new_data) { /* 1. Allocate the Node & 2. Put in the data 3. Set next as null */ Node new_node = new Node(new_data); /* 4. If the Linked List is empty, then make the new node as head */ if (head == null) { head = new Node(new_data); return; } /* 4. This new node is going to be the last node, so make next of it as null */ new_node.next = null; /* 5. Else traverse till the last node */ Node last = head; while (last.next != null) last = last.next; /* 6. Change the next of last node */ last.next = new_node; return; } /* This function prints contents of linked list starting from the given node */ public void printList() { Node tnode = head; while (tnode != null) { Console.Write(tnode.data + " "); tnode = tnode.next; } } // Driver Code public static void Main(String[] args) { /* Start with the empty list */ GFG llist = new GFG(); // Insert 6. So linked list becomes 6->NUllist llist.append(6); // Insert 7 at the beginning. // So linked list becomes 7->6->NUllist llist.push(7); // Insert 1 at the beginning. // So linked list becomes 1->7->6->NUllist llist.push(1); // Insert 4 at the end. So linked list becomes // 1->7->6->4->NUllist llist.append(4); // Insert 8, after 7. So linked list becomes // 1->7->8->6->4->NUllist llist.insertAfter(llist.head.next, 8); Console.Write("Created Linked list is: "); llist.printList(); } }

Kết quả in ra là:

Created Linked list is: 1 7 8 6 4

Nguồn và Tài liệu tiếng anh tham khảo:

  • w3schools
  • Geeksforgeeks
  • codechef
  • dev.to

Tài liệu từ cafedev:

  • Full series tự học Cấu trúc dữ liệu và giải thuật từ cơ bản tới nâng cao tại đây nha.
  • Ebook về Cấu trúc dữ liệu và giải thuật tại đây.
  • Các series tự học lập trình khác

Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:

  • Group Facebook
  • Fanpage
  • Youtube
  • Instagram
  • Twitter
  • Linkedin
  • Pinterest
  • Trang chủ

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!

Từ khóa » Bài Tập Về Danh Sách Liên Kết đơn Trong Java