Giới thiệu
Series về cấu trúc dữ liệu và thuật toán sử dụng Golang. Ở bài này chúng ta sẽ tìm hiểu về Linked Lists.
Linked Lists
Linked Lists là một cấu trúc dữ liệu dạng collection, nó là tập họp của nhiều object được gọi là node, và các node này được nối với nhau thông qua một liên kết được gọi là link.
Linked Lists cũng tương tự như Array, nhưng ở một số ngôn ngữ khi ta làm việc với Array, thì ta thường phải đối mặt với một số vấn đề về độ dài của Array. Linked Lists sẽ giúp ta giải quyết các vấn đề đó.
Linked Lists sẽ có các hàm như sau để ta làm việc với nó:
- insert: thêm một node vào Linked Lists.
- remove: xóa một node khỏi Linked Lists.
- find: tìm một node trong Linked Lists.
- findPrevious: tìm một node mà đằng trước node khác trong Linked Lists.
- print: in ra dữ liệu của Linked Lists.
Linked Lists Implementation
Đầu tiên ta tạo một file tên là linked.go với đoạn code như sau:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | <span class="token keyword">package</span> main <span class="token keyword">type</span> Node <span class="token keyword">struct</span> <span class="token punctuation">{</span> element <span class="token keyword">interface</span><span class="token punctuation">{</span><span class="token punctuation">}</span> next <span class="token operator">*</span>Node <span class="token punctuation">}</span> <span class="token keyword">type</span> LinkedLists <span class="token keyword">struct</span> <span class="token punctuation">{</span> head <span class="token operator">*</span>Node <span class="token punctuation">}</span> <span class="token keyword">func</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token punctuation">}</span> |
Ta sẽ dùng struct để định nghĩa Node, một Node sẽ có hai thuộc tính là element và next. Với element dùng để chứa giá trị của Node, và next dùng để Node liên kết tới một Node khác.
Ta cũng sẽ dùng struct để định nghĩa Linked Lists, nó sẽ có một thuộc tính là head, đây là Node bắt đầu của Linked Lists, ta sẽ luôn phải truy cập head trước sau đó mới đi qua các Node còn lại.
Ta sẽ khởi tạo Linked Lists với một Node có element là “head”, và thuộc tính next sẽ chỉa tới một Node khác có element là null, vì trong Golang sẽ không có Constructor cho struct, nên ta sẽ dùng function để giả lập hàm Constructor cho một struct, cú pháp thông dụng của function dùng để làm Constructor trong Golang là New<StructName>.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | <span class="token keyword">package</span> main <span class="token keyword">type</span> Node <span class="token keyword">struct</span> <span class="token punctuation">{</span> element <span class="token keyword">interface</span><span class="token punctuation">{</span><span class="token punctuation">}</span> next <span class="token operator">*</span>Node <span class="token punctuation">}</span> <span class="token keyword">type</span> LinkedLists <span class="token keyword">struct</span> <span class="token punctuation">{</span> head <span class="token operator">*</span>Node <span class="token punctuation">}</span> <span class="token keyword">func</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token punctuation">}</span> <span class="token keyword">func</span> <span class="token function">NewLinkedLists</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">*</span>LinkedLists <span class="token punctuation">{</span> <span class="token keyword">return</span> <span class="token operator">&</span>LinkedLists<span class="token punctuation">{</span>head<span class="token punctuation">:</span> <span class="token operator">&</span>Node<span class="token punctuation">{</span>element<span class="token punctuation">:</span> <span class="token string">"head"</span><span class="token punctuation">,</span> next<span class="token punctuation">:</span> <span class="token operator">&</span>Node<span class="token punctuation">{</span><span class="token punctuation">}</span><span class="token punctuation">}</span><span class="token punctuation">}</span> <span class="token punctuation">}</span> |
Tiếp theo ta sẽ viết hàm insert, cập nhật linked.go.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | <span class="token keyword">package</span> main <span class="token operator">...</span> <span class="token keyword">func</span> <span class="token punctuation">(</span>l <span class="token operator">*</span>LinkedLists<span class="token punctuation">)</span> <span class="token function">Find</span><span class="token punctuation">(</span>element <span class="token keyword">interface</span><span class="token punctuation">{</span><span class="token punctuation">}</span><span class="token punctuation">)</span> <span class="token operator">*</span>Node <span class="token punctuation">{</span> current <span class="token operator">:=</span> l<span class="token punctuation">.</span>head <span class="token keyword">for</span> current<span class="token punctuation">.</span>element <span class="token operator">!=</span> element <span class="token punctuation">{</span> current <span class="token operator">=</span> current<span class="token punctuation">.</span>next <span class="token punctuation">}</span> <span class="token keyword">return</span> current <span class="token punctuation">}</span> <span class="token keyword">func</span> <span class="token punctuation">(</span>l <span class="token operator">*</span>LinkedLists<span class="token punctuation">)</span> <span class="token function">Insert</span><span class="token punctuation">(</span>newElement <span class="token keyword">interface</span><span class="token punctuation">{</span><span class="token punctuation">}</span><span class="token punctuation">,</span> element <span class="token keyword">interface</span><span class="token punctuation">{</span><span class="token punctuation">}</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token punctuation">}</span> <span class="token keyword">func</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token punctuation">}</span> <span class="token operator">...</span> |
Hàm Insert() của ta sẽ nhận vào hai giá trị là newElement và element, với element là giá trị của Node mà ta muốn thêm một Node mới vào trước nó. Và để kiếm được Node mà ta sẽ thêm một Node mới vào trước nó, ta phải dùng hàm Find().
Hàm Find() được dùng để kiếm một Node bất kì nào đó trong Linked Lists, đầu tiên ta sẽ tạo một biến tên là current và gán Head Node vào nó, sau đó ta sẽ duyệt qua từng Node và trả về Node mà có giá trị element bằng với giá trị element ta truyền vào.
Ta sẽ thực hiện hàm Insert() như sau.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | <span class="token keyword">package</span> main <span class="token operator">...</span> <span class="token keyword">func</span> <span class="token punctuation">(</span>l <span class="token operator">*</span>LinkedLists<span class="token punctuation">)</span> <span class="token function">Insert</span><span class="token punctuation">(</span>newElement <span class="token keyword">interface</span><span class="token punctuation">{</span><span class="token punctuation">}</span><span class="token punctuation">,</span> element <span class="token keyword">interface</span><span class="token punctuation">{</span><span class="token punctuation">}</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> newNode <span class="token operator">:=</span> <span class="token operator">&</span>Node<span class="token punctuation">{</span>element<span class="token punctuation">:</span> newElement<span class="token punctuation">}</span> current <span class="token operator">:=</span> l<span class="token punctuation">.</span><span class="token function">Find</span><span class="token punctuation">(</span>element<span class="token punctuation">)</span> newNode<span class="token punctuation">.</span>next <span class="token operator">=</span> current<span class="token punctuation">.</span>next current<span class="token punctuation">.</span>next <span class="token operator">=</span> newNode <span class="token punctuation">}</span> <span class="token keyword">func</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token punctuation">}</span> <span class="token operator">...</span> |
Ta khởi tạo một Node mới với giá trị newElement, và tìm kiếm Node mà ta muốn thêm Node mới vào trước nó, gán nó vào biến current. Tiếp theo ta cập nhật lại giá trị next của Node mới bằng giá trị của Node mà ta vừa kiếm được, sau đó ta gán lại giá trị next của nó để liên kết với Node mới.
Để kiểm tra được hàm Insert() của ta có hoạt động đúng không, ta viết thêm hàm print để in giá trị của Linked Lists ra thử.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | <span class="token keyword">package</span> main <span class="token operator">...</span> <span class="token keyword">func</span> <span class="token punctuation">(</span>l <span class="token operator">*</span>LinkedLists<span class="token punctuation">)</span> <span class="token function">Print</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> current <span class="token operator">:=</span> l<span class="token punctuation">.</span>head <span class="token keyword">for</span> <span class="token punctuation">{</span> fmt<span class="token punctuation">.</span><span class="token function">Printf</span><span class="token punctuation">(</span><span class="token string">"%v"</span><span class="token punctuation">,</span> current<span class="token punctuation">.</span>element<span class="token punctuation">)</span> current <span class="token operator">=</span> current<span class="token punctuation">.</span>next <span class="token keyword">if</span> current<span class="token punctuation">.</span>next <span class="token operator">==</span> <span class="token boolean">nil</span> <span class="token punctuation">{</span> fmt<span class="token punctuation">.</span><span class="token function">Println</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token keyword">break</span> <span class="token punctuation">}</span> fmt<span class="token punctuation">.</span><span class="token function">Print</span><span class="token punctuation">(</span><span class="token string">" -> "</span><span class="token punctuation">)</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token keyword">func</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token punctuation">}</span> <span class="token operator">...</span> |
Cập nhật lại linked.go để kiểm tra các hàm của ta nào.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | <span class="token keyword">package</span> main <span class="token keyword">import</span> <span class="token string">"fmt"</span> <span class="token keyword">type</span> Node <span class="token keyword">struct</span> <span class="token punctuation">{</span> element <span class="token keyword">interface</span><span class="token punctuation">{</span><span class="token punctuation">}</span> next <span class="token operator">*</span>Node <span class="token punctuation">}</span> <span class="token keyword">type</span> LinkedLists <span class="token keyword">struct</span> <span class="token punctuation">{</span> head <span class="token operator">*</span>Node <span class="token punctuation">}</span> <span class="token keyword">func</span> <span class="token punctuation">(</span>l <span class="token operator">*</span>LinkedLists<span class="token punctuation">)</span> <span class="token function">Find</span><span class="token punctuation">(</span>element <span class="token keyword">interface</span><span class="token punctuation">{</span><span class="token punctuation">}</span><span class="token punctuation">)</span> <span class="token operator">*</span>Node <span class="token punctuation">{</span> current <span class="token operator">:=</span> l<span class="token punctuation">.</span>head <span class="token keyword">for</span> current<span class="token punctuation">.</span>element <span class="token operator">!=</span> element <span class="token punctuation">{</span> current <span class="token operator">=</span> current<span class="token punctuation">.</span>next <span class="token punctuation">}</span> <span class="token keyword">return</span> current <span class="token punctuation">}</span> <span class="token keyword">func</span> <span class="token punctuation">(</span>l <span class="token operator">*</span>LinkedLists<span class="token punctuation">)</span> <span class="token function">Insert</span><span class="token punctuation">(</span>newElement <span class="token keyword">interface</span><span class="token punctuation">{</span><span class="token punctuation">}</span><span class="token punctuation">,</span> element <span class="token keyword">interface</span><span class="token punctuation">{</span><span class="token punctuation">}</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> newNode <span class="token operator">:=</span> <span class="token operator">&</span>Node<span class="token punctuation">{</span>element<span class="token punctuation">:</span> newElement<span class="token punctuation">}</span> current <span class="token operator">:=</span> l<span class="token punctuation">.</span><span class="token function">Find</span><span class="token punctuation">(</span>element<span class="token punctuation">)</span> newNode<span class="token punctuation">.</span>next <span class="token operator">=</span> current<span class="token punctuation">.</span>next current<span class="token punctuation">.</span>next <span class="token operator">=</span> newNode <span class="token punctuation">}</span> <span class="token keyword">func</span> <span class="token punctuation">(</span>l <span class="token operator">*</span>LinkedLists<span class="token punctuation">)</span> <span class="token function">Print</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> current <span class="token operator">:=</span> l<span class="token punctuation">.</span>head <span class="token keyword">for</span> <span class="token punctuation">{</span> fmt<span class="token punctuation">.</span><span class="token function">Printf</span><span class="token punctuation">(</span><span class="token string">"%v"</span><span class="token punctuation">,</span> current<span class="token punctuation">.</span>element<span class="token punctuation">)</span> current <span class="token operator">=</span> current<span class="token punctuation">.</span>next <span class="token keyword">if</span> current<span class="token punctuation">.</span>next <span class="token operator">==</span> <span class="token boolean">nil</span> <span class="token punctuation">{</span> fmt<span class="token punctuation">.</span><span class="token function">Println</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token keyword">break</span> <span class="token punctuation">}</span> fmt<span class="token punctuation">.</span><span class="token function">Print</span><span class="token punctuation">(</span><span class="token string">" -> "</span><span class="token punctuation">)</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token keyword">func</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> l <span class="token operator">:=</span> <span class="token function">NewLinkedLists</span><span class="token punctuation">(</span><span class="token punctuation">)</span> l<span class="token punctuation">.</span><span class="token function">Insert</span><span class="token punctuation">(</span><span class="token string">"Hoàng Phúc International"</span><span class="token punctuation">,</span> <span class="token string">"head"</span><span class="token punctuation">)</span> l<span class="token punctuation">.</span><span class="token function">Insert</span><span class="token punctuation">(</span><span class="token string">"Ecko"</span><span class="token punctuation">,</span> <span class="token string">"Hoàng Phúc International"</span><span class="token punctuation">)</span> l<span class="token punctuation">.</span><span class="token function">Insert</span><span class="token punctuation">(</span><span class="token string">"Kappa"</span><span class="token punctuation">,</span> <span class="token string">"Ecko"</span><span class="token punctuation">)</span> l<span class="token punctuation">.</span><span class="token function">Print</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">}</span> <span class="token keyword">func</span> <span class="token function">NewLinkedLists</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">*</span>LinkedLists <span class="token punctuation">{</span> <span class="token keyword">return</span> <span class="token operator">&</span>LinkedLists<span class="token punctuation">{</span>head<span class="token punctuation">:</span> <span class="token operator">&</span>Node<span class="token punctuation">{</span>element<span class="token punctuation">:</span> <span class="token string">"head"</span><span class="token punctuation">,</span> next<span class="token punctuation">:</span> <span class="token operator">&</span>Node<span class="token punctuation">{</span><span class="token punctuation">}</span><span class="token punctuation">}</span><span class="token punctuation">}</span> <span class="token punctuation">}</span> |
1 2 | go run linked.go |
Kết quả.
1 2 | head -> Hoàng Phúc International -> Ecko -> Kappa |
Các hàm của ta đã chạy đúng như ý ta muốn, tiếp theo ta sẽ viết hàm remove để xóa Node ra khỏi Linked Lists.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | <span class="token keyword">package</span> main <span class="token operator">...</span> <span class="token keyword">func</span> <span class="token punctuation">(</span>l <span class="token operator">*</span>LinkedLists<span class="token punctuation">)</span> <span class="token function">FindPrevious</span><span class="token punctuation">(</span>element <span class="token keyword">interface</span><span class="token punctuation">{</span><span class="token punctuation">}</span><span class="token punctuation">)</span> <span class="token operator">*</span>Node <span class="token punctuation">{</span> current <span class="token operator">:=</span> l<span class="token punctuation">.</span>head <span class="token keyword">for</span> current<span class="token punctuation">.</span>next <span class="token operator">!=</span> <span class="token boolean">nil</span> <span class="token operator">&&</span> current<span class="token punctuation">.</span>next<span class="token punctuation">.</span>element <span class="token operator">!=</span> element <span class="token punctuation">{</span> current <span class="token operator">=</span> current<span class="token punctuation">.</span>next <span class="token punctuation">}</span> <span class="token keyword">return</span> current <span class="token punctuation">}</span> <span class="token keyword">func</span> <span class="token punctuation">(</span>l <span class="token operator">*</span>LinkedLists<span class="token punctuation">)</span> <span class="token function">Remove</span><span class="token punctuation">(</span>element <span class="token keyword">interface</span><span class="token punctuation">{</span><span class="token punctuation">}</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> prevNode <span class="token operator">:=</span> l<span class="token punctuation">.</span><span class="token function">FindPrevious</span><span class="token punctuation">(</span>element<span class="token punctuation">)</span> <span class="token keyword">if</span> prevNode<span class="token punctuation">.</span>next <span class="token operator">!=</span> <span class="token boolean">nil</span> <span class="token punctuation">{</span> current <span class="token operator">:=</span> prevNode<span class="token punctuation">.</span>next prevNode<span class="token punctuation">.</span>next <span class="token operator">=</span> current<span class="token punctuation">.</span>next current <span class="token operator">=</span> <span class="token boolean">nil</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token keyword">func</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token punctuation">}</span> <span class="token operator">...</span> |
Hàm Remove() ta sẽ nhận vào giá trị element của Node mà ta muốn xóa đi, để xóa được Node ra khỏi Linked Lists ta cần làm một số bước sau, ta phải có hàm FindPrevious() để kiếm Node trước đó (prevNode) của Node mà ta muốn xóa, sau đó ta chỉ đơn giản là cập nhật lại giá trị next của prevNode, cho nó liên kết tới Node tiếp theo của Node mà ta cần xóa, Node ta xóa đi sẽ không được liên kết tới bất kì Node nào nữa.
Hàm FindPrevious() ta sẽ bắt đầu từ head và duyệt qua từng Node, để tìm kiếm Node trước đó của một Node bất kì, thay vì kiểm tra giá trị element của Node hiện tại thì ta sẽ kiểm ta giá trị element của Node kế tiếp bằng current.next.element.
Ở hàm Remove() thì sẽ lằng nhằng hơn một chút, đầu tiên ta sẽ lấy prevNode của Node mà ta muốn xóa ra, gán Node mà ta muốn xóa vào biến current. Và để xóa Node đó rất đơn giản, ta chỉ cần cập nhật lại thuộc tính next của prevNode chỉa tới current.next, lúc này prevNode sẽ không liên kết với current nữa mà sẽ liên kết với Node kế tiếp của current.
Cập nhật lại hàm main để kiểm tra xem hàm Remove() có hoạt động đúng ý ta không.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 | <span class="token keyword">package</span> main <span class="token keyword">import</span> <span class="token string">"fmt"</span> <span class="token keyword">type</span> Node <span class="token keyword">struct</span> <span class="token punctuation">{</span> element <span class="token keyword">interface</span><span class="token punctuation">{</span><span class="token punctuation">}</span> next <span class="token operator">*</span>Node <span class="token punctuation">}</span> <span class="token keyword">type</span> LinkedLists <span class="token keyword">struct</span> <span class="token punctuation">{</span> head <span class="token operator">*</span>Node <span class="token punctuation">}</span> <span class="token keyword">func</span> <span class="token punctuation">(</span>l <span class="token operator">*</span>LinkedLists<span class="token punctuation">)</span> <span class="token function">Find</span><span class="token punctuation">(</span>element <span class="token keyword">interface</span><span class="token punctuation">{</span><span class="token punctuation">}</span><span class="token punctuation">)</span> <span class="token operator">*</span>Node <span class="token punctuation">{</span> current <span class="token operator">:=</span> l<span class="token punctuation">.</span>head <span class="token keyword">for</span> current<span class="token punctuation">.</span>element <span class="token operator">!=</span> element <span class="token punctuation">{</span> current <span class="token operator">=</span> current<span class="token punctuation">.</span>next <span class="token punctuation">}</span> <span class="token keyword">return</span> current <span class="token punctuation">}</span> <span class="token keyword">func</span> <span class="token punctuation">(</span>l <span class="token operator">*</span>LinkedLists<span class="token punctuation">)</span> <span class="token function">FindPrevious</span><span class="token punctuation">(</span>element <span class="token keyword">interface</span><span class="token punctuation">{</span><span class="token punctuation">}</span><span class="token punctuation">)</span> <span class="token operator">*</span>Node <span class="token punctuation">{</span> current <span class="token operator">:=</span> l<span class="token punctuation">.</span>head <span class="token keyword">for</span> current<span class="token punctuation">.</span>next <span class="token operator">!=</span> <span class="token boolean">nil</span> <span class="token operator">&&</span> current<span class="token punctuation">.</span>next<span class="token punctuation">.</span>element <span class="token operator">!=</span> element <span class="token punctuation">{</span> current <span class="token operator">=</span> current<span class="token punctuation">.</span>next <span class="token punctuation">}</span> <span class="token keyword">return</span> current <span class="token punctuation">}</span> <span class="token keyword">func</span> <span class="token punctuation">(</span>l <span class="token operator">*</span>LinkedLists<span class="token punctuation">)</span> <span class="token function">Insert</span><span class="token punctuation">(</span>newElement <span class="token keyword">interface</span><span class="token punctuation">{</span><span class="token punctuation">}</span><span class="token punctuation">,</span> element <span class="token keyword">interface</span><span class="token punctuation">{</span><span class="token punctuation">}</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> newNode <span class="token operator">:=</span> <span class="token operator">&</span>Node<span class="token punctuation">{</span>element<span class="token punctuation">:</span> newElement<span class="token punctuation">}</span> current <span class="token operator">:=</span> l<span class="token punctuation">.</span><span class="token function">Find</span><span class="token punctuation">(</span>element<span class="token punctuation">)</span> newNode<span class="token punctuation">.</span>next <span class="token operator">=</span> current<span class="token punctuation">.</span>next current<span class="token punctuation">.</span>next <span class="token operator">=</span> newNode <span class="token punctuation">}</span> <span class="token keyword">func</span> <span class="token punctuation">(</span>l <span class="token operator">*</span>LinkedLists<span class="token punctuation">)</span> <span class="token function">Remove</span><span class="token punctuation">(</span>element <span class="token keyword">interface</span><span class="token punctuation">{</span><span class="token punctuation">}</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> prevNode <span class="token operator">:=</span> l<span class="token punctuation">.</span><span class="token function">FindPrevious</span><span class="token punctuation">(</span>element<span class="token punctuation">)</span> <span class="token keyword">if</span> prevNode<span class="token punctuation">.</span>next <span class="token operator">!=</span> <span class="token boolean">nil</span> <span class="token punctuation">{</span> current <span class="token operator">:=</span> prevNode<span class="token punctuation">.</span>next prevNode<span class="token punctuation">.</span>next <span class="token operator">=</span> current<span class="token punctuation">.</span>next current <span class="token operator">=</span> <span class="token boolean">nil</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token keyword">func</span> <span class="token punctuation">(</span>l <span class="token operator">*</span>LinkedLists<span class="token punctuation">)</span> <span class="token function">Print</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> current <span class="token operator">:=</span> l<span class="token punctuation">.</span>head <span class="token keyword">for</span> <span class="token punctuation">{</span> fmt<span class="token punctuation">.</span><span class="token function">Printf</span><span class="token punctuation">(</span><span class="token string">"%v"</span><span class="token punctuation">,</span> current<span class="token punctuation">.</span>element<span class="token punctuation">)</span> current <span class="token operator">=</span> current<span class="token punctuation">.</span>next <span class="token keyword">if</span> current<span class="token punctuation">.</span>next <span class="token operator">==</span> <span class="token boolean">nil</span> <span class="token punctuation">{</span> fmt<span class="token punctuation">.</span><span class="token function">Println</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token keyword">break</span> <span class="token punctuation">}</span> fmt<span class="token punctuation">.</span><span class="token function">Print</span><span class="token punctuation">(</span><span class="token string">" -> "</span><span class="token punctuation">)</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token keyword">func</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> l <span class="token operator">:=</span> <span class="token function">NewLinkedLists</span><span class="token punctuation">(</span><span class="token punctuation">)</span> l<span class="token punctuation">.</span><span class="token function">Insert</span><span class="token punctuation">(</span><span class="token string">"Hoàng Phúc International"</span><span class="token punctuation">,</span> <span class="token string">"head"</span><span class="token punctuation">)</span> l<span class="token punctuation">.</span><span class="token function">Insert</span><span class="token punctuation">(</span><span class="token string">"Ecko"</span><span class="token punctuation">,</span> <span class="token string">"Hoàng Phúc International"</span><span class="token punctuation">)</span> l<span class="token punctuation">.</span><span class="token function">Insert</span><span class="token punctuation">(</span><span class="token string">"Kappa"</span><span class="token punctuation">,</span> <span class="token string">"Ecko"</span><span class="token punctuation">)</span> l<span class="token punctuation">.</span><span class="token function">Print</span><span class="token punctuation">(</span><span class="token punctuation">)</span> l<span class="token punctuation">.</span><span class="token function">Remove</span><span class="token punctuation">(</span><span class="token string">"Ecko"</span><span class="token punctuation">)</span> l<span class="token punctuation">.</span><span class="token function">Print</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">}</span> <span class="token keyword">func</span> <span class="token function">NewLinkedLists</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">*</span>LinkedLists <span class="token punctuation">{</span> <span class="token keyword">return</span> <span class="token operator">&</span>LinkedLists<span class="token punctuation">{</span>head<span class="token punctuation">:</span> <span class="token operator">&</span>Node<span class="token punctuation">{</span>element<span class="token punctuation">:</span> <span class="token string">"head"</span><span class="token punctuation">,</span> next<span class="token punctuation">:</span> <span class="token operator">&</span>Node<span class="token punctuation">{</span><span class="token punctuation">}</span><span class="token punctuation">}</span><span class="token punctuation">}</span> <span class="token punctuation">}</span> |
1 2 | go run linked.go |
Kết quả.
1 2 3 | head -> Hoàng Phúc International -> Ecko -> Kappa head -> Hoàng Phúc International -> Kappa |
Oke, vậy là ta đã viết được Linked Lists thành công. Bài này sẽ là tiền đề để ta tìm hiểu bài tiếp theo: Doubly Linked Lists and Circular Linked Lists.
Real World Example
Vậy Linked Lists sẽ được sử dụng ở đâu trong thực tế và nó giúp ta giải quyết những vấn đề gì?
Linked Lists được sử dụng cho khá nhiều ứng dụng trong khoa học dữ liệu (Computer Science), ví dụ:
- Dynamic memory allocation : We use linked list of free blocks.
- Maintaining directory of names.
- Performing arithmetic operations on long integers.
- Manipulation of polynomials by storing constants in the node of linked list.
- Representing sparse matrices.
Còn trong thực tế ta có thể sử dụng Linked Lists cho các ứng dụng như:
- Image viewer.
- Previous and next page in web browser.
- Music Player.
Các ứng dụng trên thì ta không thể dùng Linked Lists bình thường được, mà ta cần dùng Doubly Linked Lists, các bạn có thể đọc để biết rõ hơn.
Kết luận
Vậy là ta đã tìm hiểu xong cách viết Linked Lists và cách sử dụng nó. Nếu có thắc mắc hoặc cần giải thích rõ thêm chỗ nào thì các bạn có thể hỏi dưới phần comment.