Last active
April 15, 2019 21:43
-
-
Save greasysock/c819d14b8af5b439b10062d6550a5fca to your computer and use it in GitHub Desktop.
A simple linked list implentation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package linkedlist | |
type LinkedListValue struct { | |
next *LinkedListValue | |
value int | |
} | |
type LinkedList struct { | |
head *LinkedListValue | |
tail *LinkedListValue | |
length int | |
} | |
// Append method | |
func (l *LinkedList) append(value int){ | |
// Create value holder | |
val := SetupLinkedListValue(value) | |
// Set tail next to new val | |
l.tail.next = &val | |
// Increase list length | |
l.length++ | |
// Set new tail | |
l.tail = &val | |
} | |
// Prepend method | |
func (l *LinkedList) prepend(value int){ | |
val := SetupLinkedListValue(value) | |
val.next = l.head | |
l.length++ | |
l.head = &val | |
l.cursor = &val | |
} | |
func (l *LinkedList) traverseToIndex(index int) (val *LinkedListValue){ | |
next := l.head | |
for i:=0; i<index+1; i++ { | |
val = next | |
next = next.next | |
} | |
return val | |
} | |
// Get method. Will get out values with cursor | |
func (l *LinkedList) get(index int) int{ | |
return l.traverseToIndex(index).value | |
} | |
func (l *LinkedList) insert(index int, value int){ | |
// Edge case check if head or tail | |
if index<=0{ | |
l.prepend(value) | |
return | |
}else if index>=l.length-1{ | |
l.append(value) | |
return | |
} | |
first:= l.traverseToIndex(index-1) | |
middle:= SetupLinkedListValue(value) | |
last:= first.next | |
first.next = &middle | |
middle.next = last | |
l.length++ | |
} | |
func SetupLinkedListValue(value int) LinkedListValue { | |
v := LinkedListValue{} | |
v.value = value | |
return v | |
} | |
// Linked list initializer | |
func NewLinkedList(startVal int) LinkedList { | |
a := LinkedList{} | |
first := SetupLinkedListValue(startVal) | |
a.head = &first | |
a.tail = &first | |
a.cursor = &first | |
a.length = 1 | |
return a | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment