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
Nội dung chính
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 4Nguồn và Tài liệu tiếng anh tham khảo:
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:
Chào thân ái và quyết thắng!
 trong series tự học về cấu trúc dữ liệu và giải thuật){kind=link}