Golang Data Structures: Linked List

Linked List cung cấp một kiểu dữ liệu gần giống với Array, nhưng nó có một lợi điểm là việc thêm các phần tử vào giữa danh sách khá dễ dàng. Đối với một Array chúng ta phải chuyển lại vị trí của các phần tử phía sau phần tử được thêm vào.

Trong khi Array lưu trữ tất cả phần tử trong cùng 1 block của vùng nhớ và đặt cạnh nhau khiến việc truy cập dữ liệu nhanh hơn. Linked List có thể chứa những phẩn tử nằm rải rác trong bộ nhớ, bằng cách lưu địa chỉ (pointer) đến phần tử tiếp theo.

Linked List cũng có một bất lợi so với Array. Đó là nếu bạn muốn tìm kiếm 1 phần tử nào nó ở giữa Linked List mà không biết địa chỉ của nó, thì bạn phải duyệt danh sách đó từ đầu cho đến khi bạn tìm được thứ mình cần.

Cách triển khai

Một Linked List được triển khai bởi những phương thức sau:

Append(t): Thêm một phần tử vào cuối danh sách.
Insert(i, t): Thêm một phần tử vào vị trí i.
RemoveAt(i): Xóa một phần tử ở vị trí i.
IndexOf(): trả về vị trí hiện tại của phần tử.
IsEmpty(): kiểm tra danh sách có đang rỗng hay không.
Size(): trả về kích thước của danh sách.
String(): trả về 1 thể hiển của phần tử dưới dạng 1 chuỗi.
Head(): trả về phần tử đầu tiên, và chúng ta có thể bắt đầu duyệt qua danh sách này.

Codes

  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
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
package linked_list

import (
	"errors"
	"fmt"
	"sync"
)

// NodeValue the type of the linked list
type NodeValue string

// Node a single node that composes the list
type Node struct {
	value NodeValue
	// pointer content address to next node
	next *Node
}

// ItemLinkedList the linked list of Items
type ItemLinkedList struct {
	head *Node
	size int
	sync.RWMutex
}

// Append adds an Item to the end of the linked list
func (ll *ItemLinkedList) Append(value NodeValue) {
	ll.Lock()
	defer ll.Unlock()

	// create a new last node
	n := &Node{value: value, next: nil}
	if ll.head == nil {
		ll.head = n
	} else {
		// iterate to find last node, then append
		last := ll.head
		for {
			if last.next == nil {
				break
			}
			last = last.next
		}
		last.next = n
	}
	ll.size++
}

// Insert adds an Item at position i
func (ll *ItemLinkedList) Insert(i int, value NodeValue) error {
	ll.Lock()
	defer ll.Unlock()

	if i < 0 || ll.size < i {
		return errors.New("index is out of bounds")
	}

	n := &Node{value: value, next: nil}
	currNode := ll.head
	if i == 0 {
		n.next = currNode
		ll.head = n
		ll.size++
		return nil
	}

	j := 0
	for {
		currNode = currNode.next
		if j == i-1 {
			break
		}
		j++
	}

	n.next = currNode.next
	currNode.next = n
	ll.size++
	return nil
}

// RemoveAt removes a node at position i
func (ll *ItemLinkedList) RemoveAt(i int) (NodeValue, error) {
	ll.Lock()
	defer ll.Unlock()

	if i < 0 || ll.size < i {
		return "", errors.New("index is out of bounds")
	}
	var nodeToRemove *Node

	node := ll.head
	j := 0
	for {
		if j == i {
			break
		}
		node = node.next
		j++
	}

	nodeToRemove = node.next
	nextNode := nodeToRemove.next
	node.next = nextNode
	nodeToRemove.next = nil
	ll.size--

	return nodeToRemove.value, nil
}

// IndexOf returns the position of the Item t
func (ll *ItemLinkedList) IndexOf(t NodeValue) int {
	ll.RLock()
	defer ll.RUnlock()

	node := ll.head
	j := 0
	for {
		if node.value == t {
			return j
		}
		if node.next == nil {
			return -1
		}
		node = node.next
		j++
	}
}

// IsEmpty returns true if the list is empty
func (ll *ItemLinkedList) IsEmpty() bool {
	ll.RLock()
	defer ll.RUnlock()
	if ll.head == nil {
		return true
	}
	return false
}

// Size returns the linked list size
func (ll *ItemLinkedList) Size() int {
	ll.RLock()
	defer ll.RUnlock()
	size := 1
	last := ll.head
	for {
		if last == nil || last.next == nil {
			break
		}
		last = last.next
		size++
	}
	return size
}

// Head returns a pointer to the first node of the list
func (ll *ItemLinkedList) Head() *Node {
	ll.RLock()
	defer ll.RUnlock()
	return ll.head
}

// Insert adds an Item at position i
func (ll *ItemLinkedList) String() {
	ll.RLock()
	defer ll.RUnlock()
	node := ll.head
	j := 0
	for {
		if node == nil {
			break
		}
		j++
		fmt.Print(node.value)
		fmt.Print(" ")
		node = node.next
	}
	fmt.Println()
}

Test

 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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
package linked_list

import (
	"fmt"
	"testing"
)

func TestAppend(t *testing.T) {
	var ll ItemLinkedList

	if !ll.IsEmpty() {
		t.Errorf("list should be empty")
	}

	ll.Append("first")
	if ll.IsEmpty() {
		t.Errorf("list should not be empty")
	}

	if size := ll.Size(); size != 1 {
		t.Errorf("wrong count, expected 1 and got %d", size)
	}

	ll.Append("second")
	ll.Append("third")

	if size := ll.Size(); size != 3 {
		t.Errorf("wrong count, expected 3 and got %d", size)
	}
}

func TestRemoveAt(t *testing.T) {
	var ll ItemLinkedList
	ll.Append("first")
	ll.Append("second")
	ll.Append("third")

	_, err := ll.RemoveAt(1)
	if err != nil {
		t.Errorf("unexpected error %s", err)
	}

	if size := ll.Size(); size != 2 {
		t.Errorf("wrong count, expected 2 and got %d", size)
	}
}

func TestInsert(t *testing.T) {
	var ll ItemLinkedList
	ll.Append("first")
	ll.Append("second")
	ll.Append("third")

	//test inserting in the middle
	err := ll.Insert(2, "second2")
	if err != nil {
		t.Errorf("unexpected error %s", err)
	}
	if size := ll.Size(); size != 4 {
		t.Errorf("wrong count, expected 4 and got %d", size)
	}

	//test inserting at head position
	err = ll.Insert(0, "zero")
	if err != nil {
		t.Errorf("unexpected error %s", err)
	}
}

func TestIndexOf(t *testing.T) {
	var ll ItemLinkedList
	ll.Append("zero")
	ll.Append("first")
	ll.Append("second2")
	ll.Append("third")

	if i := ll.IndexOf("zero"); i != 0 {
		t.Errorf("expected position 0 but got %d", i)
	}
	if i := ll.IndexOf("first"); i != 1 {
		t.Errorf("expected position 1 but got %d", i)
	}
	if i := ll.IndexOf("second2"); i != 2 {
		t.Errorf("expected position 2 but got %d", i)
	}
	if i := ll.IndexOf("third"); i != 3 {
		t.Errorf("expected position 3 but got %d", i)
	}
}

func TestHead(t *testing.T) {
	var ll ItemLinkedList
	ll.Append("zero")
	h := ll.Head()
	if "zero" != fmt.Sprint(h.value) {
		t.Errorf("Expected `zero` but got %s", fmt.Sprint(h.value))
	}
}

Ứng dụng

Hơi khó tìm các ứng dụng Linked List trong thực tế. Tuy nhiên bạn có thể sử dụng nó như một cấu trúc FIFO

Cách triển khai#

Ứng dụng#

Cách triển khai

Ứng dụng