Cấu Trúc Dữ Liệu Danh Sách Liên Kết đôi (Doubly Linked List) - VietTuts

Trang chủ » Danh Sách Liên Kết Kép Là Gì » Cấu Trúc Dữ Liệu Danh Sách Liên Kết đôi (Doubly Linked List) - VietTuts

Có thể bạn quan tâm

Cấu Trúc Dữ Liệu & Giải Thuật

Tổng quan về cấu trúc dữ liệu và giải thuật Cấu trúc dữ liệu là gì? Giải thuật là gì? Cài đặt môi trường

Giải Thuật

Giải thuật tiệm cận Giải thuật tham lam Giải thuật chia để trị Giải thuật qui hoạch động

Cấu Trúc Dữ Liệu Mảng

Cấu trúc dữ liệu mảng

Danh sách liên kết - Linked list

Cấu trúc dữ liệu Linked List Cấu trúc dữ Doubly Linked List Cấu trúc dữ Circular Linked List

Ngăn Xếp & Hàng Đợi

Cấu trúc dữ liệu ngăn xếp - Stack Cấu trúc dữ hàng dợi - Queue

Một Số Giải Thuật Tìm Kiếm

Tìm kiếm tuyến tính - Linear Search Tìm kiếm nhị phân - Binary Search Tìm kiếm nội suy - Interpolation Search Cấu trúc dữ liệu Hash Table

Một Số Giải Thuật Sắp Xếp

Giải thuật sắp xếp Sắp xếp nổi bọt - Bubble Sort Sắp xếp chèn - Insertion Sort Sắp xếp chọn - Selection Sort Sắp xếp trộn - Merge Sort Sắp xếp nhanh - Quick Sort Giải thuật Shell Sort Giải thuật quay lui - Back Tracking

Cấu Trúc Dữ Liệu Đồ Thị (Graph)

Cấu trúc dữ liệu đồ thị Tìm kiếm theo chiều sâu - Depth First Search Tìm kiếm theo chiều sâu - Breadth First Search Cấu trúc dữ liệu danh sách liên kết (Linked List) Cấu trúc dữ liệu danh sách liên kết vòng (Circular Linked List)

Nội dung chính

  • Danh sách liên kết đôi (Doubly Linked List) là gì?
  • Biểu diễn Danh sách liên kết đôi
  • Các hoạt động cơ bản trên Danh sách liên kết đôi
  • Hoạt động chèn trong Danh sách liên kết đôi
  • Hoạt động xóa trong Danh sách liên kết đôi
  • Hoạt động chèn tại vị trí cuối trong Danh sách liên kết đôi

Danh sách liên kết đôi (Doubly Linked List) là gì?

Danh sách liên kết đôi (Doubly Linked List) là một biến thể của danh sách liên kết (Linked List), trong đó hoạt động duyệt qua các nút có thể được thực hiện theo hai chiều: về trước và về sau một cách dễ dàng khi so sánh với Danh sách liên kết đơn. Dưới đây là một số khái niệm quan trọng cần ghi nhớ về Danh sách liên kết đôi.

  • Link: mỗi link của một Danh sách liên kết có thể lưu giữ một dữ liệu và được gọi là một phần tử.

  • Next: mỗi link của một Danh sách liên kết có thể chứa một link tới next link và được gọi là Next.

  • Prev: mỗi link của một Danh sách liên kết có thể chứa một link tới previous link và được gọi là Prev.

  • First và Last: một Danh sách liên kết chứa link kết nối tới first link được gọi là First và tới last link được gọi là Last.

Biểu diễn Danh sách liên kết đôi

Danh sách liên kết đôi (Doubly Linked List)

Như hình minh họa trên, bạn cần ghi nhớ:

  • Danh sách liên kết đôi chứa một phần tử link và được gọi là First và Last.
  • Mỗi link mang một trường dữ liệu và một trường link được gọi là Next.
  • Mỗi link được liên kết với phần tử kế tiếp bởi sử dụng Next Link.
  • Mỗi link được liên kết với phần tử phía trước bởi sử dụng Prev Link.
  • Last Link mang một link trỏ tới NULL để đánh dầu phần cuối của Danh sách liên kết.

Các hoạt động cơ bản trên Danh sách liên kết đôi

  • Hoạt động chèn: thêm một phần tử vào vị trí đầu của Danh sách liên kết.

  • Hoạt động xóa: xóa một phần tử tại vị trí đầu của Danh sách liên kết.

  • Hoạt động chèn vào cuối: thêm một phần tử vào vị trí cuối của Danh sách liên kết.

  • Hoạt động xóa phần tử cuối: xóa một phần tử tại vị trí cuối của Danh sách liên kết.

  • Hoạt động chèn vào sau: thêm một phần tử vào sau một phần tử của Danh sách liên kết.

  • Hoạt động xóa (bởi key): xóa một phần tử từ Danh sách liên kết bởi sử dụng khóa đã cung cấp.

  • Hiển thị danh sách về phía trước: hiển thị toàn bộ Danh sách liên kết theo chiều về phía trước.

  • Hiển thị danh sách về phía sau: hiển thị toàn bộ Danh sách liên kết theo chiều về phía sau.

Hoạt động chèn trong Danh sách liên kết đôi

Phần dưới đây là giải thuật minh họa cho hoạt động chèn tại vị trí đầu của một Danh sách liên kết đôi.

//Chèn link tại vị trí đầu tiên void insertFirst(int key, int data) { //tạo một link struct node *link = (struct node*) malloc(sizeof(struct node)); link->key = key; link->data = data; if(isEmpty()) { //Biến nó thành last link last = link; }else { //Cập nhật prev link đầu tiên head->prev = link; } //Trỏ nó tới first link cũ link->next = head; //Trỏ first tới first link mới head = link; }

Hoạt động xóa trong Danh sách liên kết đôi

Phần dưới đây là giải thuật minh họa cho hoạt động xóa phần tử tại vị trí đầu của một Danh sách liên kết đôi.

//xóa phần tử đầu tiên struct node* deleteFirst() { //Lưu tham chiếu tới first link struct node *tempLink = head; //Nếu chỉ có link if(head->next == NULL) { last = NULL; }else { head->next->prev = NULL; } head = head->next; //Trả về link đã bị xóa return tempLink; }

Hoạt động chèn tại vị trí cuối trong Danh sách liên kết đôi

Phần dưới đây là giải thuật minh họa cho hoạt động chèn tại vị trí cuối của một Danh sách liên kết đôi.

//Chèn link vào vị trí cuối cùng void insertLast(int key, int data) { //tạo một link struct node *link = (struct node*) malloc(sizeof(struct node)); link->key = key; link->data = data; if(isEmpty()) { //biến nó thành last link last = link; }else { //làm cho link trở thành last link mới last->next = link; //Đánh dấu last node là prev của new link link->prev = last; } //Trỏ last tới new last node last = link; } Cấu trúc dữ liệu danh sách liên kết (Linked List) Cấu trúc dữ liệu danh sách liên kết vòng (Circular Linked List)

Recent Updates

Xuất dữ liệu ra màn hình console trong JavaCài đặt môi trường JavaJava Swing - Bài tập quản lý sinh viên trong javaLinkedList trong javaArrayList trong javaBài tập java có lời giảiXác thực dữ liệu (Data Validation) trong ExcelSắp xếp dữ liệu trong ExcelLọc dữ liệu (Data Filter) trong ExcelHeader và Footer trong ExcelMàu văn bản và màu nền (background) trong ExcelCăn chỉnh văn bản trong ExcelSắp Tết 2024 Rồi! - Còn bao nhiêu ngày nữa là đến tết 2024?

VietTuts on facebook

Học Lập Trình Online Miễn Phí - VietTuts.Vn
Danh Sách Bài Học

Học Java | Hibernate | Spring Học Excel | Excel VBA Học Servlet | JSP | Struts2 Học C | C++ | C# Học Python Học SQL

Bài Tập Có Lời Giải

Bài tập Java Bài tập C Bài tập C++ Bài tập C# Bài tập Python Ví dụ Excel VBA

Câu Hỏi Phỏng Vấn

201 câu hỏi phỏng vấn java 25 câu hỏi phỏng vấn servlet 75 câu hỏi phỏng vấn jsp 52 câu hỏi phỏng vấn Hibernate 70 câu hỏi phỏng vấn Spring 57 câu hỏi phỏng vấn SQL

Từ khóa » Danh Sách Liên Kết Kép Là Gì