[Powered by Google Translate] Trong lập trình, chúng ta thường cần để đại diện cho danh sách các giá trị, chẳng hạn như tên của học sinh trong phần một hoặc điểm trên bài kiểm tra mới nhất. 

Trong ngôn ngữ C, tuyên bố mảng có thể được sử dụng để lưu trữ danh sách. Thật dễ dàng để liệt kê các yếu tố của một danh sách lưu trữ trong một mảng, và nếu bạn cần truy cập hoặc sửa đổi danh sách các yếu tố thứ i đối với một số chỉ số tùy ý, mà có thể được thực hiện trong thời gian liên tục, nhưng mảng có nhược điểm, quá. 

Khi chúng ta tuyên bố chúng, chúng ta cần phải nói lên phía trước họ là lớn như thế nào, có nghĩa là, họ có thể lưu trữ nhiều yếu tố và làm thế nào lớn những yếu tố này, được xác định bởi kiểu của họ. Ví dụ, int arr (10) có thể lưu trữ 10 bản ghi có kích thước của một int. 

Chúng ta không thể thay đổi kích thước của một mảng sau khi khai báo. Chúng ta phải thực hiện một mảng mới nếu chúng ta muốn lưu trữ nhiều yếu tố. Lý do hạn chế này tồn tại là chúng tôi chương trình lưu trữ toàn bộ mảng như là một đoạn tiếp giáp của bộ nhớ. Nói đây là bộ đệm mà chúng tôi lưu trữ trong mảng của chúng tôi. Có thể có các biến số khác nằm ngay bên cạnh các mảng trong bộ nhớ, do đó, chúng ta không thể chỉ cần thực hiện các mảng lớn hơn. 

Đôi khi chúng tôi muốn thương mại tốc độ nhanh chóng truy cập dữ liệu của mảng cho một ít linh hoạt hơn. Nhập danh sách liên kết, một cấu trúc dữ liệu cơ bản bạn có thể không quen thuộc với. Ở mức độ cao, một danh sách liên kết lưu trữ dữ liệu trong một chuỗi các nút được kết nối với nhau với các liên kết, vì thế cái tên "danh sách liên kết. Như chúng ta sẽ thấy, sự khác biệt trong thiết kế dẫn đến lợi thế và nhược điểm khác nhau hơn một mảng. 

Dưới đây là một số mã C cho một danh sách liên kết rất đơn giản các số nguyên. Bạn có thể thấy rằng chúng tôi đã đại diện cho mỗi nút trong danh sách như là một cấu trúc, trong đó có 2 điều, một số nguyên để lưu trữ được gọi là 'val' và một liên kết đến nút tiếp theo trong danh sách mà chúng tôi đại diện như một con trỏ được gọi là 'bên cạnh.' Bằng cách này, chúng ta có thể theo dõi toàn bộ danh sách với chỉ duy nhất một con trỏ đến nút 1, và sau đó chúng ta có thể thực hiện theo các con trỏ tiếp theo đến nút thứ 2, nút thứ 3, nút thứ 4, và như vậy, cho đến khi chúng tôi nhận được đến cuối của danh sách. 

Bạn có thể có thể thấy được 1 lợi thế này có trên cấu trúc mảng tĩnh với một danh sách liên kết, chúng ta không cần một đoạn lớn của bộ nhớ hoàn toàn. Nút 1 của danh sách có thể sống tại nơi này trong bộ nhớ, và nút thứ 2 có thể là tất cả các cách trên đây. Chúng tôi có thể nhận được tất cả các nút không có vấn đề trong bộ nhớ, bởi vì bắt đầu tại nút 1, con trỏ tiếp theo mỗi nút cho chúng ta biết chính xác nơi để đi tiếp theo. 

Ngoài ra, chúng tôi không cần phải nói lên phía trước một danh sách liên kết lớn như thế nào sẽ là cách chúng tôi làm với mảng tĩnh, kể từ khi chúng tôi có thể tiếp tục thêm các nút vào một danh sách miễn là có không gian một nơi nào đó trong bộ nhớ cho các nút mới. Do đó, danh sách liên kết dễ dàng để thay đổi kích thước tự động. Nói, trong chương trình chúng ta cần thêm các nút hơn vào danh sách của chúng tôi. Để chèn một nút mới vào danh sách của chúng tôi trên bay, tất cả chúng ta phải làm là cấp phát bộ nhớ cho nút đó, tiếng tom trong giá trị dữ liệu, và sau đó đặt nó mà chúng tôi muốn bằng cách điều chỉnh con trỏ thích hợp. 

Ví dụ, nếu chúng ta muốn đặt một nút ở giữa thứ 2 và 3 nút của danh sách,  chúng ta sẽ không phải di chuyển các nút 2 hoặc 3 ở tất cả. Nói rằng chúng tôi đang chèn nút này màu đỏ. Tất cả những gì chúng ta phải làm là đặt con trỏ tới các nút mới để trỏ đến nút thứ 3 và sau đó ReWire con trỏ tới nút thứ 2 để trỏ đến nút mới của chúng tôi. Vì vậy, chúng ta có thể thay đổi kích thước danh sách của chúng tôi trên bay kể từ khi máy tính của chúng tôi không dựa vào chỉ mục, mà thay vào liên kết sử dụng con trỏ để lưu trữ chúng. 

Tuy nhiên, một bất lợi của danh sách liên kết là, không giống như một mảng tĩnh, máy tính có thể không chỉ nhảy đến giữa của danh sách. Kể từ khi máy tính có truy cập mỗi nút trong danh sách liên kết để có được đến kế tiếp, nó sẽ mất nhiều thời gian hơn để tìm thấy một nút cụ thể hơn nó sẽ trong một mảng. Để đi qua toàn bộ danh sách cần có thời gian tỷ lệ thuận với chiều dài của danh sách, hoặc O (n) trong ký hiệu tiệm cận. Tính trung bình, đạt bất kỳ nút cũng cần có thời gian tỷ lệ thuận với n. 

Bây giờ, hãy viết một số mã làm việc với các danh sách liên kết. Hãy nói rằng chúng tôi muốn có một danh sách liên kết các số nguyên. Chúng tôi có thể đại diện cho một nút trong danh sách của chúng tôi một lần nữa như là một cấu trúc với 2 lĩnh vực, một giá trị số nguyên được gọi là 'val' và một con trỏ đến nút tiếp theo của danh sách. Vâng, có vẻ đơn giản. 

Hãy nói rằng chúng ta muốn viết một chức năng đi qua danh sách và in ra giá trị được lưu trữ trong các nút cuối cùng của danh sách. Vâng, điều đó có nghĩa là chúng tôi sẽ cần phải đi qua tất cả các nút trong danh sách để tìm người cuối cùng, nhưng vì chúng tôi không thêm hoặc xóa bất cứ điều gì, chúng tôi không muốn thay đổi cấu trúc nội bộ của các con trỏ tiếp theo trong danh sách. 

Vì vậy, chúng tôi sẽ cần một con trỏ đặc biệt cho traversal mà chúng ta sẽ gọi là "thu thập thông tin. ' Nó sẽ thu thập dữ liệu thông qua tất cả các yếu tố của danh sách theo chuỗi của con trỏ tới. Tất cả chúng tôi đã được lưu trữ một con trỏ đến nút 1, hoặc 'đầu' của danh sách. Điểm Đầu nút 1. Đó là kiểu con trỏ-to-node. 

Để có được các nút 1 thực tế trong danh sách, chúng ta phải dereference con trỏ này, nhưng trước khi chúng ta có thể dereference nó, chúng ta cần phải kiểm tra con trỏ là null đầu tiên. Nếu đó là vô giá trị, danh sách là trống rỗng, và chúng ta nên in ra một thông điệp rằng, bởi vì danh sách có sản phẩm nào, không có nút qua. Tuy nhiên, chúng ta hãy nói rằng trong danh sách là không có sản phẩm nào. Nếu không, thì chúng ta nên thu thập dữ liệu thông qua toàn bộ danh sách cho đến khi chúng tôi nhận được các nút cuối cùng của danh sách, và làm thế nào chúng ta có thể biết chúng tôi đang tìm kiếm tại các nút cuối cùng trong danh sách? 

Vâng, nếu con trỏ tới một nút là null, chúng tôi biết chúng tôi đang ở cuối tiếp theo kể từ khi con trỏ sẽ không có nút tiếp theo trong danh sách để trỏ đến. Đó là thực hành tốt để luôn luôn giữ cho con trỏ tới nút cuối cùng khởi tạo null có một tài sản được tiêu chuẩn hóa cảnh báo chúng tôi khi chúng tôi đã đạt đến cuối danh sách. 

Vì vậy, nếu thu thập thông tin → tiếp theo là null, hãy nhớ rằng cú pháp mũi tên là một phím tắt cho dereferencing một con trỏ đến một cấu trúc, sau đó truy cập trường tiếp theo của nó tương đương với vụng về: (* Bánh xích) tiếp theo. Một khi chúng ta đã tìm thấy các nút cuối cùng, chúng tôi muốn in thu thập thông tin → val, giá trị trong các nút hiện tại mà chúng ta biết là người cuối cùng. Nếu không, nếu chúng ta không được nêu ra tại các nút cuối cùng trong danh sách, chúng ta phải di chuyển đến nút tiếp theo trong danh sách và kiểm tra nếu đó là người cuối cùng. Để làm điều này, chúng ta chỉ cần đặt con trỏ trình thu thập thông tin của chúng tôi để trỏ đến giá trị tiếp theo của nút hiện tại, có nghĩa là, nút tiếp theo trong danh sách. Điều này được thực hiện bằng cách thiết lập thu thập thông tin = thu thập thông tin → sau. Sau đó, chúng ta lặp lại quá trình này, với một vòng lặp ví dụ, cho đến khi chúng tôi tìm thấy các nút cuối cùng. Vì vậy, ví dụ, nếu thu thập thông tin đã chỉ vào đầu, chúng tôi thiết lập thu thập thông tin chỉ để thu thập thông tin → tiếp theo, mà là giống như các lĩnh vực tiếp theo của nút 1. Vì vậy, bây giờ thu thập thông tin của chúng tôi được trỏ đến nút thứ 2, và, một lần nữa, chúng ta lặp lại điều này với một vòng lặp, cho đến khi chúng tôi đã tìm thấy các nút cuối cùng, đó là, nơi con trỏ tiếp theo của nút là chỉ để null. Và chúng tôi đã có nó, chúng tôi đã tìm thấy các nút cuối cùng trong danh sách, và in giá trị của nó, chúng tôi chỉ sử dụng thu thập thông tin → val. 

Traversing không phải là quá xấu, nhưng những gì về chèn? Cho phép nói rằng chúng tôi muốn chèn một số nguyên vào vị trí thứ 4 trong một danh sách số nguyên. Đó là giữa 3 và 4 nút hiện tại. Một lần nữa, chúng ta phải đi qua các danh sách chỉ để được các yếu tố thứ 3, một trong chúng tôi đang chèn sau. Vì vậy, chúng tôi tạo ra một con trỏ thu thập thông tin một lần nữa để đi qua các danh sách, kiểm tra xem con trỏ đầu của chúng tôi là vô giá trị, và nếu nó không phải, chỉ con trỏ trình thu thập thông tin của chúng tôi tại nút đầu. Vì vậy, chúng ta đang ở các yếu tố 1. Chúng tôi phải đi về phía trước thêm 2 yếu tố trước khi chúng ta có thể chèn, vì vậy chúng tôi có thể sử dụng một vòng lặp for int i = 1; i <3; i + + và trong mỗi lần lặp của vòng lặp, tiến trình thu thập thông tin của chúng tôi con trỏ về phía trước bằng 1 nút bằng cách kiểm tra nếu trường tiếp theo của nút hiện tại là null, và nếu nó không phải, di chuyển con trỏ trình thu thập thông tin của chúng tôi đến nút tiếp theo bằng cách thiết lập nó bằng con trỏ tới các nút hiện tại. Vì vậy, kể từ khi vòng lặp cho chúng tôi nói rằng để làm điều đó hai lần, chúng tôi đã đạt đến nút thứ 3, và một khi con trỏ trình thu thập thông tin của chúng tôi đã đạt đến các nút sau khi mà chúng tôi muốn để chèn số nguyên mới của chúng tôi, làm thế nào để chúng tôi thực sự làm các việc chèn? 

Vâng, nguyên mới của chúng tôi đã được đưa vào danh sách như là một phần của struct node riêng của mình, vì đây thực sự là một chuỗi các nút. Vì vậy, chúng ta hãy làm một con trỏ mới đến nút được gọi là 'new_node, và thiết lập nó để trỏ đến bộ nhớ mà bây giờ chúng ta phân bổ trên heap cho nút chính nó, và chúng ta cần phải phân bổ bao nhiêu bộ nhớ? , Kích thước của một nút, và chúng tôi muốn thiết lập lĩnh vực val đến số nguyên mà chúng tôi muốn chèn. Hãy nói rằng, 6. Bây giờ, nút chứa giá trị số nguyên của chúng tôi. Nó cũng tốt thực hành để khởi tạo trường tiếp theo của nút mới chỉ để null, nhưng bây giờ những gì? 

Chúng ta phải thay đổi cấu trúc nội bộ của danh sách và các con trỏ tiếp theo chứa hiện tại của danh sách Thứ 3 và thứ 4 nút. Kể từ khi con trỏ tiếp theo xác định thứ tự của danh sách, và kể từ khi chúng tôi đang chèn nút mới của chúng tôi ngay chính giữa của danh sách, nó có thể được một chút khôn lanh. Điều này là bởi vì, hãy nhớ rằng, máy tính của chúng tôi chỉ biết vị trí của các nút trong danh sách vì các con trỏ tiếp theo được lưu trữ trong các nút trước đó. Vì vậy, nếu chúng ta bao giờ mất theo dõi của bất kỳ các địa điểm này, nói bằng cách thay đổi một số các con trỏ tiếp theo trong danh sách của chúng tôi, Ví dụ, nếu chúng ta thay đổi nút thứ 3 trường tiếp theo để trỏ đến một số nút trên đây. Chúng tôi muốn được ra khỏi may mắn, bởi vì chúng tôi sẽ không có bất kỳ ý tưởng nơi để tìm thấy phần còn lại của danh sách, và đó rõ ràng là thực sự xấu. Vì vậy, chúng ta phải thực sự cẩn thận về đơn đặt hàng trong đó chúng ta thao tác con trỏ tiếp theo của chúng tôi trong quá trình chèn. 

Vì vậy, để đơn giản hóa điều này, chúng ta hãy nói rằng 4 đầu tiên của chúng tôi các nút được gọi là A, B, C, và D, với các mũi tên đại diện cho chuỗi các con trỏ kết nối các nút. Vì vậy, chúng ta cần để chèn nút mới của chúng tôi giữa các nút C và D. Đó là quan trọng để làm điều đó theo thứ tự đúng, và tôi sẽ cho bạn thấy lý do tại sao. 

Hãy nhìn vào con đường sai để làm điều đó đầu tiên. Này, chúng tôi biết các nút mới đã đến ngay sau khi C, do đó, chúng ta hãy đặt con trỏ tới C chỉ new_node. Được rồi, có vẻ okay, chúng tôi chỉ cần có để hoàn thành bây giờ bằng cách điểm con trỏ tới nút mới đến D, nhưng chờ đợi, làm thế nào chúng ta có thể làm điều đó? Điều duy nhất mà có thể cho chúng tôi biết trong đó D, con trỏ tiếp theo được lưu trữ trước đó trong C, nhưng chúng tôi chỉ viết lại con trỏ để trỏ đến các nút mới, vì vậy chúng tôi không có bất kỳ mối trong đó D là trong bộ nhớ, và chúng tôi đã bị mất phần còn lại của danh sách. Không tốt ở tất cả. 

Vì vậy, làm thế nào để chúng tôi làm điều này đúng không? Đầu tiên, chỉ con trỏ tới các nút mới tại D. Bây giờ, cả hai nút mới và C tiếp theo con trỏ đang trỏ đến cùng một nút, D, nhưng đó là tiền phạt. Bây giờ chúng tôi có thể chỉ cho con trỏ tới C tại các nút mới. Vì vậy, chúng tôi đã làm điều này mà không bị mất bất kỳ dữ liệu nào. Trong mã, C là nút hiện tại traversal con trỏ thu thập thông tin được trỏ đến, và D được đại diện bởi các nút được trỏ đến bởi trường tiếp theo của nút hiện tại, hoặc thu thập thông tin → tiếp theo. Vì vậy, chúng tôi lần đầu tiên thiết lập con trỏ tới các nút mới chỉ để thu thập thông tin → tiếp theo, theo cùng một cách chúng tôi đã nói con trỏ tới new_node trỏ đến D trong hình minh hoạ. Sau đó, chúng ta có thể đặt con trỏ tới các nút hiện tại nút mới của chúng tôi, cũng giống như chúng tôi đã phải chờ đợi đến điểm C để new_node trong các bản vẽ. Bây giờ tất cả mọi thứ theo thứ tự, và chúng tôi đã không mất theo dõi bất kỳ dữ liệu nào, và chúng tôi đã có thể chỉ cần dính nút mới của chúng tôi ở giữa của danh sách mà không cần xây dựng lại toàn bộ điều hoặc thậm chí thay đổi bất kỳ yếu tố cách chúng ta đã có thể có với một mảng có độ dài cố định. 

Vì vậy, danh sách liên kết là một cấu trúc dữ liệu động cơ bản, nhưng quan trọng trong đó có cả ưu và nhược điểm so với mảng và cấu trúc dữ liệu khác, và như thường là trường hợp trong khoa học máy tính, điều quan trọng cần biết khi sử dụng mỗi công cụ, vì vậy bạn có thể chọn đúng công cụ cho công việc phải. 

Đối với thực hành nhiều hơn, hãy thử viết chức năng xóa các nút từ một danh sách liên kết nhớ phải cẩn thận về thứ tự mà bạn sắp xếp lại Con trỏ tiếp theo của bạn để đảm bảo rằng bạn không bị mất một đoạn danh sách của bạn - hoặc một chức năng để tính các nút trong một danh sách liên kết, hoặc một niềm vui, để đảo ngược thứ tự của tất cả các nút trong một danh sách liên kết. 

Tên tôi là Jackson Steinkamp, ​​đây là CS50.