Hướng dẫn cách sử dụng danh sách liên kết trong C hiệu quả

Trong quá trình tìm hiểu về ngôn ngữ C thì danh sách liên kết là một trong những vấn đề được nhiều người quan tâm nhất hiện nay. Trên thực tế hầu hết các hướng dẫn đều đưa ra những đoạn mã có độ dài khổng lồ khiến những người mới bắt đầu sẽ cảm thấy khó khăn.

Do đó bạn phải xem xét cách con trỏ quan trọng trong danh sách được liên kết, cách cấu trúc được tạo ra và cách lưu trữ dữ liệu động được tạo ra để đảm bảo rằng việc phân bổ không gian bộ nhớ hiệu quả trong việc thực hiện lưu trữ dữ liệu. Vậy danh sách liên kết trong C được thể hiện như thế nào thì cùng Box.edu tìm hiểu ngay nhé!

Xem thêm: Hướng dẫn cách tìm nạp chuỗi trong hàm C fgets chính xác

Xem thêm: Cách đơn giản để chuyển đổi sáng giá trị số – C String to Int

Xem thêm: Tổng quan kiến thức về lập trình hướng đối tượng trong C

Tổng quan danh sách liên kết trong C

Tổng quan danh sách liên kết trong C

Danh sách liên kết được biết đến là một trong những phương pháp tốt nhất để cấp phát bộ nhớ động. Nhiều sinh viên hỏi rằng liệu mảng có được sử dụng dễ dàng hơn không. Trên thực tế thì mảng sẽ yêu cầu cấp phát bộ nhớ ngay từ đầu, trong khi danh sách liên kết trong C được phân bổ và sử dụng bộ nhớ khi đang di chuyển. Một đoạn mã nhỏ để tạo một danh sách được liên kết như sau:

struct test_linkedlist
{
    int val;
    struct test_linkedlist * next;
};

Điều này sẽ tạo ra một cấu trúc chứa một giá trị ‘val’ và một con trỏ để trỏ đến một cấu trúc tương tự.

Đặc biệt với nhà lập trình viên cần có kiến ​​thức cơ bản về con trỏ đối với danh sách được liên kết. Một con trỏ mà trỏ đến một vị trí trong bộ nhớ. Danh sách được liên kết bao gồm nút có giá trị hoặc dữ liệu riêng mà chúng phải mang theo và thêm một con trỏ được đính kèm “ĐIỂM” vào nút tiếp theo. Để có thể xem nó ở định dạng đơn giản, bạn nên đi theo các bước thực hiện sau:

Với tất cả những bước ở trên thì thông tin hệ thập lục phân là không quan trọng. Nó chỉ là một vị trí ngẫu nhiên có mặt trong bộ nhớ mà tại đây nút tiếp theo bắt đầu và con trỏ hiện tại đang trỏ đến.

Ví dụ về danh sách liên kết trong C

Dưới đây là một ví dụ thể hiện rõ hơn về danh sách liên kết này. Nếu bạn lưu trữ tên của những người làm việc trong một tòa nhà cụ thể, bạn sẽ dễ dàng đoán được số người trong đó. Nếu trường hợp thông tin liên quan đến chúng cần được lưu trữ, thì việc này sẽ đơn giản hơn nhiều nếu sử dụng các mảng đơn giản. Tuy nhiên, nếu bạn lưu trữ thông tin về các loại hàng hóa khác nhau trong cửa hàng tạp hóa lân cận, thì ở đây số lượng hàng hóa sẽ rất lớn, do vậy một danh sách được liên kết sẽ phù hợp hơn nhiều.

Đặc biệt vào những thời kỳ mà ngành công nghiệp máy tính và thiết bị điện tử không có bộ nhớ lớn. Thì việc sử dụng một danh sách liên kết đơn giản, được tạo lập bằng các cấu trúc lưu trữ thông tin về các loại hàng hóa khác nhau trong chuỗi cửa hàng tạp hóa.  

Chỉ cần bạn cung cấp thông tin cần thiết về: tên, giá cả và số lượng cụ thể. Dù với số lượng nhiều đến đâu thì các loại hàng hóa mới cũng sẽ được ưu tiên giới thiệu trước. Như vậy hàng hóa cũ khác sẽ bị loại bỏ dần. Lúc này thay vì trực tiếp đưa mã cấp cao, chúng ta hãy xem cách này. Có thể đạt được hiệu quả như thế nào trong một định dạng sơ đồ đơn giản.

Không giống như mảng, các cấu trúc trong danh sách liên kết sẽ không được đánh số nhưng chúng được liên kết với nhau bằng cách sử dụng con trỏ cung cấp địa chỉ của cấu trúc tiếp theo. Do vậy nếu bạn có địa chỉ của cấu trúc đầu tiên, thì bạn có thể đi đến bất kỳ phần nào của danh sách liên kết thông qua việc lặp lại.

Cụ thể bạn chỉ cần cung cấp địa chỉ của cấu trúc đầu tiên trong khi NULL biểu thị rằng nó là phần cuối của danh sách được liên kết. Điều quan trọng là bạn phải có kiến ​​thức sâu hơn về con trỏ. 

Ưu nhược điểm khi sử dụng danh sách liên kết trong C

Trên thực tế ngoài những lợi ích mà nó được sử dụng rộng rãi trong ngôn ngữ lập trình C thì sẽ có những nhược điểm riêng trong quá trình sử dụng. Nắm được ưu nhược điểm của danh sách liên kết trong C sẽ giúp các bạn nhận định và áp dụng nó trong việc học ngôn ngữ C một cách chính xác và hiệu quả nhất.

Ưu điểm

• Đây là cấu trúc bộ nhớ động mà nó có thể mở rộng hoặc thu nhỏ khi chạy
• Ngoài ra các bạn có thể thực hiện các thao tác khác nhau như: chèn, xóa, chỉnh sửa dễ dàng hơn rất nhiều
• Không cần cấp phát trước bộ nhớ, do đó việc sử dụng bộ nhớ hiệu quả hơn

Nhược điểm

• Gây lãng phí bộ nhớ vì sử dụng con trỏ. Chúng sẽ chiếm thêm không gian không giống như mảng, do đó nếu biết chính xác số lượng cấu trúc thì nên sử dụng mảng
• Truy cập ngẫu nhiên là không thể. Trong mảng, một lệnh gọi [n] đơn giản là đủ để nhận giá trị tuy nhiên trong danh sách liên kết, việc duyệt qua toàn bộ danh sách được liên kết là điều cần thiết
• Do các vị trí bộ nhớ không liền nhau, nó làm cho thời gian phức tạp hơn trong việc truy cập chúng. Trong mảng, thời gian truy cập là O (1) trong khi trong danh sách liên kết là O (n).
• Việc di chuyển theo hướng ngược lại rất khó trong các danh sách liên kết đơn lẻ. Ngay cả khi sử dụng danh sách liên kết đôi. Vẫn có thêm những chi phí cho các con trỏ quay lại.

Hướng dẫn xóa mục ra khỏi danh sách liên kết trong C

Hướng dẫn xóa mục ra khỏi danh sách liên kết trong C

Trong một chuỗi liên kết nếu muốn thêm, bớt mục ra khỏi danh sách thì nên làm thế nào? Cùng tìm hiểu ngay nhé! Trong một vài trường hợp, nó cần phải được xóa và giải phóng bộ nhớ mà chúng đã sử dụng. Các bạn có thể dễ dàng làm điều này bằng cách chỉ con trỏ NEXT của mục 2 vào đầu mục 4. Cụ thể như sau:

Cách thêm một mục mới trong danh sách liên kết

Để có thể thêm một mục với vào danh sách liên kết. Thì nó có thể được thực hiện ở bất kỳ vị trí nào trong danh sách. Chỉ bằng cách trỏ con trỏ TIẾP THEO của mục trước đó vào đầu của mục đó. Và con trỏ của chính nó tới mục tiếp theo trong danh sách. Bạn có thể thêm một mục mới theo cách này tại bất kỳ điểm nào. Trong danh sách được liên kết. Ví dụ nếu cửa hàng phát triển trong vòng 4 – 5 năm. Từ một cửa hàng 100 mặt hàng đơn giản lên đến hơn 10.000. Mặt hàng thì việc thêm hoặc bớt các mặt hàng trên thực tế cũng được thực hiện một cách dễ dàng.

Do đó, nếu cần thêm bất kỳ thông tin nào về danh sách liên kết trong C. Hoặc các chủ đề cao hơn thì giờ có thể thực hiện theo những cách cơ bản. Mà chúng tôi đề cập trên ví dụ như sau:

Bình thường

0

SAI

SAI

SAI

VI-US

X-KHÔNG

X-KHÔNG

/ * Định nghĩa phong cách * /

table.MsoNormalTable

{mso-style-name: “Bảng Bình thường”;

mso-tstyle-rowband-size: 0;

mso-tstyle-colband-size: 0;

mso-style-noshow: vâng;

mso-style-priority: 99;