Back to home

Setting up the testTrees implementationRunning Tests
Go Linked List main image

Go Linked List

Basic unidirectional linked lists with Golang.

Setting up the test

Set up linked_list_test.go with the following file:

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 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 package linkedlist import ( "testing" ) func TestInsertFirst(t *testing.T) { for _, tt := range insertFirstTestCases { t.Log(tt.description) l := List{} l.insertFirst(&tt.input) if tt.expectedLen != l.size { t.Errorf("FAIL: Return value expected %d but got %d", tt.expectedLen, l.size) return } if tt.expectedData != l.head.data { t.Errorf("FAIL: Return value expected %d but got %d", tt.expectedData, l.head.data) return } hasNext := l.head.next != nil if tt.expectedNext != hasNext { t.Errorf("FAIL: Return value expected %d but got %d", tt.expectedData, l.head.data) return } t.Logf("PASS: Expected length %d and got %d", tt.expectedLen, l.size) t.Logf("PASS: Expected data %d and got %d", tt.expectedData, l.head.data) t.Logf("PASS: Expected data %t and got %t", tt.expectedNext, hasNext) } } func TestInsertFirstFromArray(t *testing.T) { l := List{} n1 := Node{data: 12} n2 := Node{data: 2} n3 := Node{data: 8} l.insertFirst(&n1) l.insertFirst(&n2) l.insertFirst(&n3) if &n3 != l.head { t.Errorf("FAIL: First list value expected %+v but got %+v", &n3, l.head) return } t.Logf("PASS: First list value expected %+v but got %+v", &n3, l.head) } func TestInsertLastFromArray(t *testing.T) { l := List{} n1 := Node{data: 12} n2 := Node{data: 2} n3 := Node{data: 8} l.insertLast(&n1) l.insertLast(&n2) l.insertLast(&n3) last := l.getLast() if &n3 != last { t.Errorf("FAIL: Last list value expected %+v but got %+v", &n3, l.head) return } t.Logf("PASS: Last list value expected %+v but got %+v", &n3, l.head) } func TestGetFirst(t *testing.T) { for _, tt := range getFirstTestCases { t.Log(tt.description) l := List{} l.insertFirst(&tt.input) firstNode := l.getFirst() if firstNode != &tt.input { t.Errorf("FAIL: Return value expected %+v but got %+v", &tt.input, firstNode) return } t.Logf("PASS: Expected %+v and got %+v", &tt.input, firstNode) } } func TestClearList(t *testing.T) { l := List{} n1 := Node{data: 12} n2 := Node{data: 2} n3 := Node{data: 8} l.insertLast(&n1) l.insertLast(&n2) l.insertLast(&n3) l.clear() if l.head != nil { t.Errorf("FAIL: Last list value expected nil but got %+v", l.head) return } t.Logf("PASS: Last list value expected nil and got %+v", l.head) } func TestGetNodeAtIndexOfList(t *testing.T) { l := List{} n1 := Node{data: 12} n2 := Node{data: 2} n3 := Node{data: 8} l.insertLast(&n1) l.insertLast(&n2) l.insertLast(&n3) res, err := l.getAt(1) if err != nil { t.Errorf("FAIL: Return error from GetNodeAtIndex") return } if &n2 != res { t.Errorf("FAIL: Get list value expected %+v but got %+v", &n2, res) return } t.Logf("PASS: Get list value expected %+v and got %+v", &n2, res) } func TestRemoveNodeAtIndexOfList(t *testing.T) { l := List{} n1 := Node{data: 12} n2 := Node{data: 2} n3 := Node{data: 8} l.insertLast(&n1) l.insertLast(&n2) l.insertLast(&n3) err := l.removeAt(1) res, getErr := l.getAt(1) if err != nil { t.Errorf("FAIL: Return error from GetNodeAtIndex") return } if getErr != nil { t.Errorf("FAIL: Return error from GetNodeAtIndex") return } if &n3 != res { t.Errorf("FAIL: Post-removed list value expected %+v but got %+v", &n3, res) return } t.Logf("PASS: Post-removed list value expected %+v and got %+v", &n3, res) } func TestInsertNodeAtIndexOfList(t *testing.T) { l := List{} n1 := Node{data: 12} n2 := Node{data: 2} n3 := Node{data: 8} n4 := Node{data: 123} l.insertLast(&n1) l.insertLast(&n2) l.insertLast(&n3) err := l.insertAt(1, &n4) if err != nil { t.Errorf("FAIL: Return error from GetNodeAtIndex") return } res, getErr := l.getAt(1) if getErr != nil { t.Errorf("FAIL: Return error from GetNodeAtIndex") return } if &n4 != res { t.Errorf("FAIL: Insert list value expected %+v but got %+v", &n4, res) return } t.Logf("PASS: Insert list value expected %+v and got %+v", &n4, res) }

Trees implementation

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 /* @author Dennis O'Keeffe Methods: 1. insertFirst: Insert at the head of list 2. size: Fetch size 3. getFirst: Fetch the first node 4. getLast: Fetch the last node 5. clear: Remove all node 6. removeFirst: Remove head of list 7. removeLast: Remove last node 8. insertLast: Insert at end of list 9. getAt: Fetch node at index 10. removeAt: Remove node at index 11. insertAt: Insert at index 12. forEach: Iterate through list and run function on list */ package linkedlist import ( "errors" "sync" ) // Node - Setup base node type for linked list type Node struct { data int next *Node } // List - Basic singularly linked list type List struct { head *Node size int lock sync.Mutex } func (l *List) insertFirst(n *Node) { l.lock.Lock() if l.head != nil { tmp := l.head l.head = n n.next = tmp } else { l.head = n } l.size++ l.lock.Unlock() } func (l *List) insertLast(n *Node) { l.lock.Lock() if l.head == nil { l.head = n } else { last := l.head for { if last.next == nil { break } last = last.next } last.next = n } l.size++ l.lock.Unlock() } func (l *List) getFirst() *Node { return l.head } func (l *List) getLast() *Node { l.lock.Lock() n := l.head for { if n.next == nil { break } n = n.next } l.lock.Unlock() return n } func (l *List) clear() { l.lock.Lock() l.head = nil l.lock.Unlock() } func (l *List) getAt(index int) (*Node, error) { if l.head == nil { return nil, errors.New("No elements in list") } l.lock.Lock() i := 0 n := l.head for { if i == index { break } if n.next == nil { return nil, errors.New("No elements in list") } i++ n = n.next } l.lock.Unlock() return n, nil } func (l *List) removeAt(index int) error { if l.head == nil { return errors.New("No elements at index found in list") } l.lock.Lock() n := l.head i := 0 for { if i == index-1 { tmp := n.next.next n.next = tmp break } if n.next == nil { return errors.New("Out of range") } n = n.next } l.lock.Unlock() return nil } func (l *List) insertAt(index int, node *Node) error { if l.head == nil { return errors.New("No elements at index found in list") } l.lock.Lock() n := l.head i := 0 for { if i == index-1 { tmp := n.next.next n.next = node node.next = tmp break } if n.next == nil { return errors.New("Out of range") } n = n.next } l.lock.Unlock() return nil }

Running Tests

In the directory, run go test.

Dennis O'Keeffe

@dennisokeeffe92
  • Melbourne, Australia

Hi, I am a professional Software Engineer. Formerly of Culture Amp, UsabilityHub, Present Company and NightGuru.
I am currently working on workingoutloud.dev, Den Dribbles and LandPad .

Related articles


1,200+ PEOPLE ALREADY JOINED ❤️️

Get fresh posts + news direct to your inbox.

No spam. We only send you relevant content.