Data Structures: 3. Linked List
Mar 26, 2022
Introduction #
A linked list is literally that, a list where each item is linked to the next one. So if you have a linked list with the following items (1, 2, 3, 4) it would look like this:
flowchart LR; H(["HEAD"]) --> A([1]); A([1]) --> B([2]); B([2]) --> C([3]); C([3]) --> D([4]); D([4]) --> E(["NIL"])
The operations available on a linked list can vary - in this case we provide a function to check to see if the linked list is empty or not, a function to get the length of the list, a function to get the items without removing them, a function to list the items without removing them, a function to search the linked list, as well as functions to add or remove items from the front of the list, the back of the list, as well as a specified position in the list.
Solution #
package main
import "fmt"
type Node struct {
data any
next *Node
}
type LinkedList struct {
head *Node
}
func (l *LinkedList) IsEmpty() bool {
if l.head == nil {
return true
}
return false
}
func (l *LinkedList) Length() int {
if l.head == nil {
return 0
}
count := 1
current := l.head
for current.next != nil {
current = current.next
count += 1
}
return count
}
func (l *LinkedList) List() {
tmp := []any{}
current := l.head
tmp = append(tmp, current.data)
for current.next != nil {
current = current.next
tmp = append(tmp, current.data)
}
fmt.Printf("Nodes: %+v\n", tmp)
}
func (l *LinkedList) Get() []any {
tmp := []any{}
current := l.head
tmp = append(tmp, current.data)
for current.next != nil {
current = current.next
tmp = append(tmp, current.data)
}
return tmp
}
func (l *LinkedList) Search(term any) any {
current := l.head
if current.data == term {
return current.data
}
for current.next != nil {
current = current.next
if current.data == term {
return current.data
}
}
return nil
}
func (l *LinkedList) Push(value any) {
n := &Node{}
n.data = value
n.next = nil
current := &Node{}
if l.head == nil {
l.head = n
} else {
current = l.head
for current.next != nil {
current = current.next
}
}
current.next = n
}
func (l *LinkedList) PushAt(index int, value any) {
at := 0
n := &Node{}
n.data = value
n.next = nil
current := &Node{}
if l.head == nil {
l.head = n
} else {
current = l.head
for current.next != nil {
at++
if index == at {
if current.next != nil {
n.next = current.next
}
current.next = n
break
}
current = current.next
}
}
}
func (l *LinkedList) PushBack(value any) {
n := &Node{}
n.data = value
n.next = nil
if l.head == nil {
l.head = n
} else {
n.next = l.head
l.head = n
}
}
func (l *LinkedList) Pop() {
current := l.head
for current.next != nil {
if current.next.next != nil {
current = current.next
continue
}
break
}
current.next = nil
}
func (l *LinkedList) PopAt(index int) {
at := 0
current := l.head
if index == 0 {
l.PopBack()
return
}
for current.next != nil {
at++
if at == index {
if current.next != nil {
current.next = current.next.next
break
}
}
current = current.next
}
}
func (l *LinkedList) PopBack() {
if l.head != nil {
if l.head.next == nil {
l.head = nil
} else {
l.head = l.head.next
}
} else {
fmt.Println("Linked list is empty")
}
}
func main() {
fmt.Println("Create a new linked list")
l := &LinkedList{}
fmt.Printf("Length of list: %d\n", l.Length())
fmt.Printf("List is empty?: %v\n", l.IsEmpty())
fmt.Println("Push seven items into the list")
fmt.Println("('One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven')")
l.Push("One")
l.Push("Two")
l.Push("Three")
l.Push("Four")
l.Push("Five")
l.Push("Six")
l.Push("Seven")
fmt.Println("Display the list")
l.List()
fmt.Printf("Length of list: %d\n", l.Length())
fmt.Printf("List is empty?: %v\n", l.IsEmpty())
fmt.Println("Search the list")
fmt.Printf("Find 'One': %v\n", l.Search("One"))
fmt.Printf("Find 'Seven': %v\n", l.Search("Seven"))
fmt.Printf("Find 'Ten': %v\n", l.Search("Ten"))
fmt.Println("Test getting the entire list")
fmt.Printf("List = %+v\n", l.Get())
fmt.Println("Pop the last item from the list")
l.Pop()
l.List()
fmt.Println("Pop the first item from the list")
l.PopBack()
l.List()
fmt.Println("Pop the third item from the list (first item is item 0)")
l.PopAt(2)
l.List()
fmt.Println("Pop the fourth item from the list")
l.PopAt(3)
l.List()
fmt.Println("Pop the first item from the list")
l.PopAt(0)
l.List()
fmt.Println("Push an item (1) at the start of the list")
l.PushBack(1)
l.List()
fmt.Println("Push an item (2) into the list at position 1 in the list")
l.PushAt(1, 2)
l.List()
fmt.Println("Push an item (4) into the list at position 3 in the list")
l.PushAt(3, 4)
l.List()
fmt.Println("Push an item (6) at the end of the list")
l.Push(6)
l.List()
fmt.Println("Trying searching for an integer item")
fmt.Printf("Find 4: %v\n", l.Search(4))
}
Testing #
Create a new linked list
Length of list: 0
List is empty?: true
Push seven items into the list
('One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven')
Display the list
Nodes: [One Two Three Four Five Six Seven]
Length of list: 7
List is empty?: false
Search the list
Find 'One': One
Find 'Seven': Seven
Find 'Ten': <nil>
Test getting the entire list
List = [One Two Three Four Five Six Seven]
Pop the last item from the list
Nodes: [One Two Three Four Five Six]
Pop the first item from the list
Nodes: [Two Three Four Five Six]
Pop the third item from the list (first item is item 0)
Nodes: [Two Three Five Six]
Pop the fourth item from the list
Nodes: [Two Three Five]
Pop the first item from the list
Nodes: [Three Five]
Push an item (1) at the start of the list
Nodes: [1 Three Five]
Push an item (2) into the list at position 1 in the list
Nodes: [1 2 Three Five]
Push an item (4) into the list at position 3 in the list
Nodes: [1 2 Three 4 Five]
Push an item (6) at the end of the list
Nodes: [1 2 Three 4 Five 6]
Trying searching for an integer item
Find 4: 4