Thông tin là tất cả xung quanh chúng ta.

Trong thế giới phần mềm, cách chúng ta chọn để tổ chức thông tin của mình là một nửa trận chiến. Tuy nhiên, đây là vấn đề : có rất nhiều cách để giải quyết một vấn đề. Và khi nói đến việc tổ chức dữ liệu của chúng tôi, có rất nhiều công cụ có thể hoạt động cho công việc. Bí quyết là biết công cụ nào là thích hợp để sử dụng.

Bất kể chúng ta bắt đầu viết mã bằng ngôn ngữ nào, một trong những điều đầu tiên chúng ta gặp phải là cấu trúc dữ liệu , là những cách khác nhau mà chúng ta có thể tổ chức dữ liệu của mình; biến , mảng , băm và đối tượng là tất cả các kiểu cấu trúc dữ liệu. Nhưng đây vẫn chỉ là phần nổi của tảng băng khi nói đến cấu trúc dữ liệu; có rất nhiều thứ khác, một số trong số đó bắt đầu nghe có vẻ siêu phức tạp khi bạn càng nghe về chúng.

Một trong những điều phức tạp đối với tôi luôn là danh sách liên kết . Tôi đã biết về danh sách được liên kết trong một vài năm nay, nhưng tôi không bao giờ có thể giữ chúng thẳng trong đầu. Tôi chỉ thực sự nghĩ về họ khi tôi chuẩn bị (hoặc đôi khi, ở giữa) một cuộc phỏng vấn kỹ thuật và ai đó hỏi tôi về họ. Tôi sẽ thực hiện một nghiên cứu nhỏ và nghĩ rằng tôi hiểu chúng nói về điều gì, nhưng sau một vài tuần, tôi lại quên chúng đi. Toàn bộ điều này là khá kém hiệu quả, và tất cả đều bắt nguồn từ thực tế là tôi biết chúng tồn tại, nhưng về cơ bản tôi không hiểu chúng! Vì vậy, đã đến lúc thay đổi điều đó và trả lời câu hỏi: dù sao thì danh sách liên kết là cái quái gì?

Cấu trúc dữ liệu tuyến tính

Nếu chúng ta thực sự muốn hiểu những điều cơ bản về danh sách liên kết, điều quan trọng là chúng ta phải nói về kiểu cấu trúc dữ liệu của chúng.

Một đặc điểm của danh sách được liên kết là chúng là cấu trúc dữ liệu tuyến tính , có nghĩa là có một trình tự và thứ tự cách chúng được xây dựng và duyệt qua. Chúng ta có thể coi cấu trúc dữ liệu tuyến tính giống như trò chơi nhảy lò cò : để đi đến cuối danh sách, chúng ta phải xem qua tất cả các mục trong danh sách theo thứ tự hoặc tuần tự . Cấu trúc tuyến tính, tuy nhiên, ngược lại với cấu trúc phi tuyến tính. Trong cấu trúc dữ liệu phi tuyến tính , các mục không cần phải được sắp xếp theo thứ tự, có nghĩa là chúng ta có thể duyệt cấu trúc dữ liệu không theo trình tự .

Không phải lúc nào chúng ta cũng nhận ra điều đó, nhưng tất cả chúng ta đều làm việc với các cấu trúc dữ liệu tuyến tính và phi tuyến tính hàng ngày! Khi chúng tôi tổ chức dữ liệu của mình thành các hàm băm (đôi khi được gọi là từ điển ), chúng tôi đang triển khai cấu trúc dữ liệu phi tuyến tính. Cây và đồ thị cũng là những cấu trúc dữ liệu phi tuyến tính mà chúng ta duyệt theo nhiều cách khác nhau, nhưng chúng ta sẽ nói sâu hơn về chúng vào cuối năm.

Tương tự, khi chúng ta sử dụng mảng trong mã của mình, chúng ta đang triển khai cấu trúc dữ liệu tuyến tính! Có thể hữu ích khi nghĩ về các mảng và danh sách được liên kết giống nhau theo cách chúng ta sắp xếp dữ liệu. Trong cả hai cấu trúc này, thứ tự quan trọng . Nhưng điều gì làm cho mảng và danh sách liên kết khác nhau?

Quản lý bộ nhớ

Điểm khác biệt lớn nhất giữa mảng và danh sách được liên kết là cách chúng sử dụng bộ nhớ trong máy của chúng ta. Những người trong chúng ta làm việc với các ngôn ngữ được nhập động như Ruby, JavaScript hoặc Python không phải nghĩ về việc một mảng sử dụng bao nhiêu bộ nhớ khi chúng ta viết mã hàng ngày vì có một số lớp trừu tượng cuối cùng với chúng tôi không phải lo lắng về việc cấp phát bộ nhớ.

Nhưng điều đó không có nghĩa là phân bổ bộ nhớ không xảy ra! Trừu tượng không phải là ma thuật, nó chỉ là sự đơn giản của việc che giấu những thứ mà bạn không cần phải nhìn thấy hoặc xử lý mọi lúc. Ngay cả khi chúng ta không phải suy nghĩ về việc cấp phát bộ nhớ khi viết mã, nếu chúng ta muốn thực sự hiểu những gì đang xảy ra trong một danh sách được liên kết và điều gì làm cho nó trở nên mạnh mẽ, chúng ta phải xuống cấp độ thô sơ.

Chúng ta đã học về hệ nhị phân và cách dữ liệu có thể được chia thành các bit và byte. Cũng giống như các ký tự, số, từ, câu yêu cầu byte bộ nhớ để biểu diễn chúng, cấu trúc dữ liệu cũng vậy.

Khi một mảng được tạo, nó cần một lượng bộ nhớ nhất định. Nếu chúng ta có 7 chữ cái cần lưu trữ trong một mảng, chúng ta sẽ cần 7 byte bộ nhớ để biểu diễn mảng đó. Nhưng, chúng ta cần tất cả bộ nhớ đó trong một khối liền kề . Điều đó có nghĩa là, máy tính của chúng ta sẽ cần định vị 7 byte bộ nhớ trống, một byte bên cạnh byte khác, tất cả cùng một chỗ.

Mặt khác, khi một danh sách được liên kết được sinh ra, nó không cần 7 byte bộ nhớ tất cả ở một nơi. Một byte có thể sống ở một nơi nào đó, trong khi byte tiếp theo có thể được lưu trữ ở một nơi khác trong bộ nhớ hoàn toàn! Danh sách được liên kết không cần chiếm một khối bộ nhớ; thay vào đó, bộ nhớ mà họ sử dụng có thể bị phân tán khắp nơi .

Sự khác biệt cơ bản giữa mảng và danh sách liên kết là mảng là cấu trúc dữ liệu tĩnh , trong khi danh sách liên kết là cấu trúc dữ liệu động . Cấu trúc dữ liệu tĩnh cần tất cả tài nguyên của nó được cấp phát khi cấu trúc được tạo; điều này có nghĩa là ngay cả khi cấu trúc được phát triển hoặc thu nhỏ về kích thước và các phần tử được thêm vào hoặc loại bỏ, nó vẫn luôn cần một kích thước và dung lượng bộ nhớ nhất định. Nếu cần thêm nhiều phần tử vào cấu trúc dữ liệu tĩnh và nó không có đủ bộ nhớ, ví dụ: bạn cần sao chép dữ liệu của mảng đó và tạo lại nó với nhiều bộ nhớ hơn để bạn có thể thêm các phần tử vào nó.

Mặt khác, cấu trúc dữ liệu động có thể thu nhỏ và phát triển trong bộ nhớ. Nó không cần một lượng bộ nhớ nhất định được cấp phát để tồn tại, kích thước và hình dạng của nó có thể thay đổi và lượng bộ nhớ nó cần cũng có thể thay đổi.

Bây giờ, chúng ta đã có thể bắt đầu thấy một số khác biệt chính giữa mảng và danh sách được liên kết. Nhưng điều này đặt ra câu hỏi: điều gì cho phép một danh sách được liên kết có bộ nhớ của nó nằm rải rác khắp nơi? Để trả lời câu hỏi này, chúng ta cần xem xét cách cấu trúc một danh sách liên kết.

Các phần của danh sách được liên kết

Một danh sách liên kết có thể nhỏ hoặc lớn, nhưng bất kể kích thước, các phần tạo nên nó thực sự khá đơn giản. Danh sách liên kết được tạo thành từ một loạt các nút , là các phần tử của danh sách.

Điểm bắt đầu của danh sách là một tham chiếu đến nút đầu tiên, được gọi là phần đầu . Gần như tất cả các danh sách được liên kết đều phải có phần đầu, vì đây thực sự là điểm vào duy nhất cho danh sách và tất cả các phần tử của nó, và nếu không có nó, bạn sẽ không biết bắt đầu từ đâu! Phần cuối của danh sách không phải là một nút, mà là một nút trỏ đến null hoặc một giá trị trống.

Một nút duy nhất cũng khá đơn giản. Nó chỉ có hai phần: dữ liệu hoặc thông tin mà nút chứa và một tham chiếu đến nút tiếp theo .

Nếu chúng ta có thể hiểu được điều này, thì chúng ta đã đi được một nửa. Cách thức hoạt động của các nút là siêu quan trọng và siêu mạnh, và có thể được tóm tắt như sau:

Một nút chỉ biết về dữ liệu mà nó chứa và người hàng xóm của nó là ai.

Một nút duy nhất không biết danh sách được liên kết dài bao nhiêu và thậm chí nó có thể không nhất thiết biết nó bắt đầu từ đâu hoặc kết thúc ở đâu. Tất cả những gì một nút quan tâm là dữ liệu mà nó chứa và con trỏ của nó tham chiếu đến nút nào - nút tiếp theo trong danh sách.

Và đây là lý do tại sao một danh sách liên kết không cần một khối bộ nhớ liền kề. Bởi vì một nút duy nhất có “địa chỉ” hoặc một tham chiếu đến nút tiếp theo, chúng không cần phải nằm ngay cạnh nhau, theo cách mà các phần tử phải có trong một mảng. Thay vào đó, chúng ta chỉ có thể dựa vào thực tế là chúng ta có thể duyệt qua danh sách của mình bằng cách dựa vào các tham chiếu con trỏ đến nút tiếp theo, điều đó có nghĩa là máy của chúng ta không cần phải chặn một đoạn bộ nhớ để thể hiện danh sách của chúng ta.

Đây cũng là lời giải thích tại sao danh sách liên kết có thể phát triển và thu nhỏ động trong quá trình thực thi chương trình. Việc thêm hoặc xóa một nút với danh sách được liên kết trở nên đơn giản như việc sắp xếp lại một số con trỏ, thay vì sao chép qua các phần tử của một mảng! Tuy nhiên, cũng có một số hạn chế đối với danh sách được liên kết mà tôi chưa đề cập đến bạn - nhưng sẽ có nhiều hạn chế hơn vào tuần tới.

Bây giờ, chúng ta sẽ chỉ đắm chìm trong vinh quang của danh sách được liên kết thú vị như thế nào!

Danh sách cho tất cả các hình dạng và kích thước

Mặc dù các phần của danh sách được liên kết không thay đổi, nhưng cách chúng tôi cấu trúc danh sách được liên kết của mình có thể hoàn toàn khác. Giống như hầu hết mọi thứ trong phần mềm, tùy thuộc vào vấn đề mà chúng tôi đang cố gắng giải quyết, một loại danh sách được liên kết có thể là công cụ tốt hơn cho công việc hơn loại khác.

Danh sách liên kết đơn là loại danh sách liên kết đơn giản nhất, chỉ dựa trên thực tế là chúng chỉ đi theo một hướng. Có một bản nhạc duy nhất mà chúng ta có thể xem qua danh sách; chúng tôi bắt đầu từ những người đứng đầu nút, và đi qua từ gốc cho đến khi cuối cùng nút, mà sẽ kết thúc tại một trống rỗng giá trị.

Nhưng cũng giống như một nút có thể tham chiếu đến nút hàng xóm tiếp theo của nó, nó cũng có thể có một con trỏ tham chiếu đến nút trước đó! Đây là những gì chúng tôi gọi là danh sách được liên kết kép , bởi vì có hai tham chiếu chứa trong mỗi nút: một tham chiếu đến nút tiếp theo , cũng như nút trước đó . Điều này có thể hữu ích nếu chúng tôi muốn có thể duyệt qua cấu trúc dữ liệu của mình không chỉ theo một hướng hoặc một hướng duy nhất mà còn cả ngược lại.

Ví dụ: nếu chúng ta muốn có thể nhảy giữa một nút và nút trước đó mà không phải quay lại đầu danh sách , thì danh sách được liên kết kép sẽ là cấu trúc dữ liệu tốt hơn so với danh sách được liên kết đơn lẻ. Tuy nhiên, mọi thứ đều yêu cầu không gian và bộ nhớ, vì vậy nếu nút của chúng ta phải lưu trữ hai con trỏ tham chiếu thay vì chỉ một, đó sẽ là một điều khác cần xem xét.

Một danh sách liên kết hình tròn là một chút kỳ lạ ở chỗ nó không kết thúc với một trỏ nút đến một giá trị null. Thay vào đó, nó có một nút đóng vai trò là phần đuôi của danh sách (chứ không phải là nút đầu thông thường) và nút sau nút đuôi là phần đầu của danh sách. Cấu trúc tổ chức này giúp bạn thực sự dễ dàng thêm thứ gì đó vào cuối danh sách, bởi vì bạn có thể bắt đầu duyệt qua nó ở nút đuôi , khi phần tử đầu tiên và phần tử cuối cùng trỏ đến nhau. Danh sách liên kết vòng có thể bắt đầu trở nên thực sự điên rồ vì chúng ta có thể biến cả danh sách được liên kết đơn lẻ và danh sách được liên kết kép thành danh sách liên kết vòng tròn!

Nhưng cho dù danh sách liên kết có phức tạp đến đâu, nếu chúng ta có thể nhớ các nguyên tắc cơ bản của một nút và cách nó hoạt động cũng như cách cấu trúc các tham chiếu con trỏ khác nhau trong danh sách của chúng ta, thì không có danh sách liên kết nào mà chúng ta không thể giải quyết!

Tuần tới, trong phần 2 của loạt bài này, chúng ta sẽ tìm hiểu kỹ về độ phức tạp không gian thời gian của các danh sách được liên kết và cách chúng so sánh với người anh em họ của chúng, mảng. Tôi hứa rằng nó thực sự thú vị hơn rất nhiều so với âm thanh!

Tài nguyên

Nếu bạn cho rằng danh sách được liên kết là quá tuyệt, hãy xem các tài nguyên hữu ích này.

1. Sự khác biệt giữa Mảng và Danh sách được Liên kết , Damien Wintour
2. Cấu trúc dữ liệu: Mảng so với Danh sách được liên kết , trường học của tôi
3. Danh sách liên kết: Khái niệm cơ bản , Tiến sĩ Edward Gehringer
4. Giới thiệu về Danh sách được Liên kết , Tiến sĩ Victor Adamchik
5. Cấu trúc & Triển khai Dữ liệu , Tiến sĩ Jennifer Welch
6. Cấu trúc dữ liệu tĩnh so với Cấu trúc dữ liệu động , Ayoma Gayan Wijethunga