Skip to content

Instantly share code, notes, and snippets.

@gabrielbussolo
Last active September 8, 2023 13:22
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save gabrielbussolo/4cbd4b6905249eed210e5c9e73d8e4f9 to your computer and use it in GitHub Desktop.
Save gabrielbussolo/4cbd4b6905249eed210e5c9e73d8e4f9 to your computer and use it in GitHub Desktop.
Singly linked list implementation in golang
package main
import (
"fmt"
)
func main() {
linkedList := NewLinkedList(10)
linkedList.Append(11)
linkedList.Append(112)
linkedList.Append(1234)
linkedList.Append(934843)
linkedList.Prepend(1)
linkedList.Prepend(60)
linkedList.Insert(2, 999)
linkedList.Insert(0, 888)
linkedList.Insert(8, 888)
linkedList.Remove(2)
fmt.Println("size: ", linkedList.Lenght())
next := linkedList.Head()
for next != nil {
fmt.Println(next.Value)
next = next.Next
}
}
type LinkedList struct {
nodes *Node
head *Node
tail *Node
lenght int
}
type Node struct {
Value int
Next *Node
}
func NewLinkedList(firstValue int) LinkedList {
firstNode := &Node{Value: firstValue, Next: nil}
return LinkedList{
nodes: firstNode,
head: firstNode,
tail: firstNode,
lenght: 1,
}
}
func (l *LinkedList) Append(value int) {
newNode := &Node{Value: value, Next: nil}
l.tail.Next = newNode
l.tail = newNode
l.lenght++
}
func (l *LinkedList) Prepend(value int) {
newNode := &Node{Value: value, Next: l.head}
l.head = newNode
l.lenght++
}
func (l *LinkedList) Insert(position, value int) {
if position < 0 || position > l.lenght {
return
}
if position == 0 {
l.Prepend(value)
return
}
if l.lenght-position == 1 {
l.Append(value)
return
}
newNode := &Node{Value: value, Next: nil}
current := l.Head()
last := l.Head()
var counter int
for current != nil {
if counter == position {
newNode.Next = last.Next
last.Next = newNode
break
}
last = current
current = current.Next
counter++
}
l.lenght++
}
func (l *LinkedList) Remove(position int) {
current := l.Head()
if position == 0 {
l.head = current.Next
current.Next = nil
return
}
latest := l.Head()
var counter int
for current != nil {
if position == counter {
latest.Next = current.Next
current.Next = nil
break
}
latest = current
current = current.Next
counter++
}
l.lenght--
}
func (l *LinkedList) Head() *Node {
return l.head
}
func (l *LinkedList) Tail() *Node {
return l.tail
}
func (l *LinkedList) Lenght() int {
return l.lenght
}
package main
import (
"testing"
)
func TestLinkedList(t *testing.T) {
t.Run("Test NewLinkedList", func(t *testing.T) {
ll := NewLinkedList(1)
if ll.Lenght() != 1 {
t.Errorf("Expected length: 1, got: %d", ll.Lenght())
}
if ll.Head().Value != 1 {
t.Errorf("Expected head value: 1, got: %d", ll.Head().Value)
}
if ll.Tail().Value != 1 {
t.Errorf("Expected tail value: 1, got: %d", ll.Tail().Value)
}
})
t.Run("Test Append", func(t *testing.T) {
ll := NewLinkedList(1)
ll.Append(2)
if ll.Lenght() != 2 {
t.Errorf("Expected length: 2, got: %d", ll.Lenght())
}
if ll.Tail().Value != 2 {
t.Errorf("Expected tail value: 2, got: %d", ll.Tail().Value)
}
})
t.Run("Test Prepend", func(t *testing.T) {
ll := NewLinkedList(1)
ll.Prepend(0)
if ll.Lenght() != 2 {
t.Errorf("Expected length: 2, got: %d", ll.Lenght())
}
if ll.Head().Value != 0 {
t.Errorf("Expected head value: 0, got: %d", ll.Head().Value)
}
})
t.Run("Test Insert", func(t *testing.T) {
ll := NewLinkedList(1)
ll.Insert(1, 2)
if ll.Lenght() != 2 {
t.Errorf("Expected length: 2, got: %d", ll.Lenght())
}
if ll.Head().Next.Value != 2 {
t.Errorf("Expected head's next value: 2, got: %d", ll.Head().Next.Value)
}
})
t.Run("Test Remove", func(t *testing.T) {
ll := NewLinkedList(1)
ll.Append(2)
ll.Remove(0)
if ll.Lenght() != 1 {
t.Errorf("Expected length: 1, got: %d", ll.Lenght())
}
if ll.Head().Value != 2 {
t.Errorf("Expected head value: 2, got: %d", ll.Head().Value)
}
})
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment