Company name
Company name
Quay lại

Circular linked list là gì?

2023-07-30 01:27:16     990 Lượt xem     69 Lượt thích
Noun Algorithm
  • ★
  • ★
  • ★
  • ★
  • ★
Danh sách liên kết vòng

Danh sách liên kết vòng (circular linked list) là một biến thể của danh sách liên kết (linked list) trong đó phần tử (element) / nút (node) cuối cùng trỏ đến phần tử / nút đầu tiên tạo thành một vòng tròn. Nói cách khác, biến thể này của danh sách liên kết không có phần tử null (null element ) ở cuối (end).. Danh sách liên kết vòng (circular linked list) có thể là danh sách liên kết đơn vòng (circular singly linked list) hoặc danh sách liên kết đôi vòng (circular doubly linked list). Ở bài viết này chúng ta sẽ lấy ví dụ về danh sách liên kết đơn vòng,

Ở đây, nút đơn được biểu diễn dưới dạng:


struct Node {
    int data;
    struct Node * next;
};

Mỗi nút có một mục dữ liệu (data item) và một con trỏ (pointer) đến nút tiếp theo. Bây giờ chúng ta sẽ tạo một danh sách liên kết vòng (circular linked list) đơn giản với ba nút để hiểu cách này hoạt động. 


/* Initialize nodes */
struct node *last;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;

/* Allocate memory */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));

/* Assign data values */
one->data = 1;
two->data = 2;
three->data = 3;

/* Connect nodes */
one->next = two;
two->next = three;
three->next = one;

/* Save address of third node in last */
last = three;

Trong đoạn mã trên, one, two, và three là các nút có các mục dữ liệu 1, 2 và 3 tương ứng.

Đối với nút one

next lưu trữ địa chỉ (address) của two (không có nút nào trước nó)

Đối với nút two

next lưu trữ địa chỉ của three

Đối với nút threee

next lưu trữ NULL (không có nút nào sau nó), next trỏ đến nút one.

Chèn trong danh sách liên kết vòng (circular linked list)

Chúng ta có thể chèn các phần tử ở 3 vị trí khác nhau của danh sách liên kết vòng:

  • Chèn ở đầu
  • Chèn ở giữa các nút
  • Chèn ở cuối

Giả sử chúng ta có một danh sách liên kết vòng với các phần tử 1, 2 và 3.

Chúng ta sẽ thêm một nút có giá trị 6 tại các vị trí khác nhau của danh sách liên kết vòng mà chúng ta đã thực hiện ở trên. Bước đầu tiên là tạo một nút mới.

  • Cấp phát (allocate) bộ nhớ cho newNode
  • Gán (assign) dữ liệu cho newNode

1. Chèn vào đầu

  • Lưu trữ địa chỉ của nút đầu tiên hiện tại trong newNode (tức là trỏ newNode đến nút đầu tiên hiện tại)
  • Trỏ nút cuối cùng đến newNode (tức là tạo newNode làm head)

2. Chèn vào giữa hai nút

Hãy chèn newNode sau nút đầu tiên.

  • Đi đến nút đã cho (đặt nút này là p)
  • Trỏ next của newNode đến nút bên cạnh p
  • Lưu trữ địa chỉ của newNode ở bên cạnh p

3. Chèn ở cuối

  • Lưu trữ địa chỉ của nút head vào next của newNode (biến newNode trở thành nút cuối cùng)
  • Trỏ nút cuối cùng hiện tại đến newNode
  • Tạo newNode làm nút cuối cùng

Xóa trên danh sách liên kết vòng

Giả sử chúng ta có một danh sách liên kết với các phần tử 1, 2 và 3.

1. Nếu nút bị xóa là nút duy nhất

  • Giải phóng (free) bộ nhớ (memory) bị chiếm bởi nút
  • Lưu trữ NULL trong last

2. Nếu nút cuối cùng bị xóa

  • Tìm nút trước nút cuối cùng (hãy để nó temp)
  • Lưu trữ địa chỉ của nút bên cạnh nút cuối cùng trong temp
  • Giải phóng bộ nhớ của last
  • Tạo temp như nút cuối cùng

3. Nếu có bất kỳ nút nào khác sẽ bị xóa

  • Di chuyển đến nút sẽ bị xóa (ở đây chúng ta đang xóa nút 2)
  • Để nút trước nút 2 là temp
  • Lưu trữ địa chỉ của nút bên cạnh 2 trong temp
  • Giải phóng bộ nhớ của 2

Mã danh sách liên kết vòng bằng C

// C code to perform circular linked list operations

#include 
#include 

struct Node {
  int data;
  struct Node* next;
};

struct Node* addToEmpty(struct Node* last, int data) {
  if (last != NULL) return last;

  // allocate memory to the new node
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

  // assign data to the new node
  newNode->data = data;

  // assign last to newNode
  last = newNode;

  // create link to iteself
  last->next = last;

  return last;
}

// add node to the front
struct Node* addFront(struct Node* last, int data) {
  // check if the list is empty
  if (last == NULL) return addToEmpty(last, data);

  // allocate memory to the new node
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

  // add data to the node
  newNode->data = data;

  // store the address of the current first node in the newNode
  newNode->next = last->next;

  // make newNode as head
  last->next = newNode;

  return last;
}

// add node to the end
struct Node* addEnd(struct Node* last, int data) {
  // check if the node is empty
  if (last == NULL) return addToEmpty(last, data);

  // allocate memory to the new node
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

  // add data to the node
  newNode->data = data;

  // store the address of the head node to next of newNode
  newNode->next = last->next;

  // point the current last node to the newNode
  last->next = newNode;

  // make newNode as the last node
  last = newNode;

  return last;
}

// insert node after a specific node
struct Node* addAfter(struct Node* last, int data, int item) {
  // check if the list is empty
  if (last == NULL) return NULL;

  struct Node *newNode, *p;

  p = last->next;
  do {
  // if the item is found, place newNode after it
  if (p->data == item) {
    // allocate memory to the new node
    newNode = (struct Node*)malloc(sizeof(struct Node));

    // add data to the node
    newNode->data = data;

    // make the next of the current node as the next of newNode
    newNode->next = p->next;

    // put newNode to the next of p
    p->next = newNode;

    // if p is the last node, make newNode as the last node
    if (p == last) last = newNode;
    return last;
  }

  p = p->next;
  } while (p != last->next);

  printf("\nThe given node is not present in the list");
  return last;
}

// delete a node
void deleteNode(struct Node** last, int key) {
  // if linked list is empty
  if (*last == NULL) return;

  // if the list contains only a single node
  if ((*last)->data == key && (*last)->next == *last) {
  free(*last);
  *last = NULL;
  return;
  }

  struct Node *temp = *last, *d;

  // if last is to be deleted
  if ((*last)->data == key) {
  // find the node before the last node
  while (temp->next != *last) temp = temp->next;

  // point temp node to the next of last i.e. first node
  temp->next = (*last)->next;
  free(*last);
  *last = temp->next;
  }

  // travel to the node to be deleted
  while (temp->next != *last && temp->next->data != key) {
  temp = temp->next;
  }

  // if node to be deleted was found
  if (temp->next->data == key) {
  d = temp->next;
  temp->next = d->next;
  free(d);
  }
}

void traverse(struct Node* last) {
  struct Node* p;

  if (last == NULL) {
  printf("The list is empty");
  return;
  }

  p = last->next;

  do {
  printf("%d ", p->data);
  p = p->next;

  } while (p != last->next);
}

int main() {
  struct Node* last = NULL;

  last = addToEmpty(last, 6);
  last = addEnd(last, 8);
  last = addFront(last, 2);

  last = addAfter(last, 10, 2);

  traverse(last);

  deleteNode(&last, 8);

  printf("\n");

  traverse(last);

  return 0;
}

Độ phức tạp (complexity) của danh sách liên kết vòng

1. Độ phức tạp của hoạt động chèn

  • Các hoạt động chèn không yêu cầu duyệt (traverse) có độ phức tạp về thời gian (time complexity) là O(1).
  • Và một hoạt động chèn yêu cầu duyệt có độ phức tạp thời gian là O(n).
  • Độ phức tạp của không gian (space complexity ) là O (1).

2. Độ phức tạp của hoạt động xóa

  • Tất cả các hoạt động xóa chạy với độ phức tạp về thời gian là O(1).
  • Và độ phức tạp không gian là O(1)
Learning English Everyday