Danh sách liên kết (Linked List)

Linked List là gì?

Linked List là cấu trúc dữ liệu gồm các node kết nối với nhau bằng con trỏ (pointer). Mỗi node chứa dữ liệu và địa chỉ của node tiếp theo.


┌──────┬──────┐    ┌──────┬──────┐    ┌──────┬──────┐
│  10  │ next │───▶│  20  │ next │───▶│  30  │ null │
└──────┴──────┘    └──────┴──────┘    └──────┴──────┘
     Head                                   Tail

💡

Linked List như một đoàn tàu - mỗi toa (node) chứa hàng hóa (data) và móc nối với toa sau!

Cài đặt Node

Python


class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
# Tạo linked list: 1 -> 2 -> 3
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

Kotlin


class Node(var data: Int, var next: Node? = null)
 
// Tạo linked list: 1 -> 2 -> 3
val head = Node(1)
head.next = Node(2)
head.next?.next = Node(3)

Dart


class Node {
  int data;
  Node? next;
  Node(this.data, [this.next]);
}
 
// Tạo linked list: 1 -> 2 -> 3
var head = Node(1);
head.next = Node(2);
head.next!.next = Node(3);

Swift


class Node {
    var data: Int
    var next: Node?
    init(_ data: Int) { self.data = data }
}
 
// Tạo linked list: 1 -> 2 -> 3
let head = Node(1)
head.next = Node(2)
head.next?.next = Node(3)

Java


class Node {
    int data;
    Node next;
    Node(int data) { this.data = data; }
}
 
// Tạo linked list: 1 -> 2 -> 3
Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);

Duyệt Linked List

Python


def traverse(head):
    current = head
    while current:
        print(current.data, end=" -> ")
        current = current.next
    print("null")

Kotlin


fun traverse(head: Node?) {
    var current = head
    while (current != null) {
        print("${current.data} -> ")
        current = current.next
    }
    println("null")
}

Dart


void traverse(Node? head) {
  Node? current = head;
  while (current != null) {
    stdout.write("${current.data} -> ");
    current = current.next;
  }
  print("null");
}

Swift


func traverse(_ head: Node?) {
    var current = head
    while current != nil {
        print("\(current!.data) -> ", terminator: "")
        current = current?.next
    }
    print("null")
}

Java


void traverse(Node head) {
    Node current = head;
    while (current != null) {
        System.out.print(current.data + " -> ");
        current = current.next;
    }
    System.out.println("null");
}

Đảo ngược Linked List

Python


def reverse(head):
    prev = None
    current = head
    
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    
    return prev  # New head

Kotlin


fun reverse(head: Node?): Node? {
    var prev: Node? = null
    var current = head
    
    while (current != null) {
        val nextNode = current.next
        current.next = prev
        prev = current
        current = nextNode
    }
    return prev
}

Dart


Node? reverse(Node? head) {
  Node? prev = null;
  Node? current = head;
  
  while (current != null) {
    Node? nextNode = current.next;
    current.next = prev;
    prev = current;
    current = nextNode;
  }
  return prev;
}

Swift


func reverse(_ head: Node?) -> Node? {
    var prev: Node? = nil
    var current = head
    
    while current != nil {
        let nextNode = current?.next
        current?.next = prev
        prev = current
        current = nextNode
    }
    return prev
}

Java


Node reverse(Node head) {
    Node prev = null;
    Node current = head;
    
    while (current != null) {
        Node nextNode = current.next;
        current.next = prev;
        prev = current;
        current = nextNode;
    }
    return prev;
}

Tìm điểm giữa (Floyd’s Algorithm)

Python


def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

Kotlin


fun findMiddle(head: Node?): Node? {
    var slow = head
    var fast = head
    while (fast?.next != null) {
        slow = slow?.next
        fast = fast.next?.next
    }
    return slow
}

Dart


Node? findMiddle(Node? head) {
  Node? slow = head, fast = head;
  while (fast?.next != null) {
    slow = slow?.next;
    fast = fast?.next?.next;
  }
  return slow;
}

Swift


func findMiddle(_ head: Node?) -> Node? {
    var slow = head, fast = head
    while fast?.next != nil {
        slow = slow?.next
        fast = fast?.next?.next
    }
    return slow
}

Java


Node findMiddle(Node head) {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

Phát hiện vòng lặp

Python


def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

Kotlin


fun hasCycle(head: Node?): Boolean {
    var slow = head
    var fast = head
    while (fast?.next != null) {
        slow = slow?.next
        fast = fast.next?.next
        if (slow === fast) return true
    }
    return false
}

Dart


bool hasCycle(Node? head) {
  Node? slow = head, fast = head;
  while (fast?.next != null) {
    slow = slow?.next;
    fast = fast?.next?.next;
    if (slow == fast) return true;
  }
  return false;
}

Swift


func hasCycle(_ head: Node?) -> Bool {
    var slow = head, fast = head
    while fast?.next != nil {
        slow = slow?.next
        fast = fast?.next?.next
        if slow === fast { return true }
    }
    return false
}

Java


boolean hasCycle(Node head) {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

So sánh với Array

Thao tác	Array	Linked List
Truy cập theo index	O(1) ✅	O(n) ❌
Thêm/xóa đầu	O(n) ❌	O(1) ✅
Thêm/xóa cuối	O(1) ✅	O(n) hoặc O(1)*
Bộ nhớ	Liên tục	Phân tán

Tiếp theo: Ngăn xếp (Stack)