Singly Linked List

Singly Linked List (Danh sách liên kết đơn) là một danh sách bao gồm các node chứa 2 thông tin: giá trị và địa chỉ đến node tiếp theo.

Singly Linked List sẽ có node head và node tail giữ vai trò ghi dấu node đầu và node cuối của danh sách, dễ dàng trong việc thêm, xoá node ở đầu hoặc cuối.

Thêm node vào đầu (Insert node to head)

def addToHead():
	input = new Node # initialize new Node
	input.next = head # the next node is the current head
	input = head # set the input as head
	
	#### Time complexity: O(1)

Xoá node ở đầu (Remove node at head)

def deleteHead():
	head = head.next

#### Time complexity: O(1)

Cách xoá khá đơn giản, do theo quy tắc Garbage Collector, nếu một vùng nhớ không được bất kì pointer nào chỉ tới, nó sẽ tự động xoá khỏi bộ nhớ (nghĩa là trong người hợp này, không có node nào chỉ tới node head hiện tại và node head đó cũng không chỉ tới bất kì node nào khác)

Thêm node vào cuối (Insert node to tail)

def addToTail():
	input = new Node # initialize new Node
	tail.next = input # the next of tail is the input
	input = tail # set the input as the tail
	
	#### Time complexity: O(1)

Xoá node ở cuối (Remove node at tail)

def deleteTail():
	node = head 
	while node.next != tail: # trace from begining
		node = node.next
	
	node.next = null # node is the previous node of tail, set next is null
	tail = node # set node as tail
	
	#### Time complexity: O(n)

Độ phức tạp

• addToHead: O(1)
• removeHead: O(1)
• addToTail: O(1)
• removeTail: O(n)
• insertNode: O(1) —- like addToTail
• deleteNode(Node x): O(n)