Created
September 8, 2023 12:09
-
-
Save aleury/abb9efb8f90ad9b97571937f3bdfa94a to your computer and use it in GitHub Desktop.
Linked List in Go
This file contains hidden or 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
| // You can edit this code! | |
| // Click here and start typing. | |
| package main | |
| import "fmt" | |
| type Node[T any] struct { | |
| Value T | |
| Next *Node[T] | |
| } | |
| type LinkedList[T any] struct { | |
| Head *Node[T] | |
| Tail *Node[T] | |
| Count int | |
| } | |
| func (l *LinkedList[T]) AddHead(n *Node[T]) { | |
| n.Next = l.Head | |
| l.Head = n | |
| l.Count++ | |
| if l.Count == 1 { | |
| l.Tail = l.Head | |
| } | |
| } | |
| func (l *LinkedList[T]) RemoveHead() { | |
| if l.Count == 0 { | |
| return | |
| } | |
| l.Head = l.Head.Next | |
| l.Count-- | |
| } | |
| func (l *LinkedList[T]) AddTail(n *Node[T]) { | |
| if l.Count == 0 { | |
| l.Head = n | |
| l.Tail = n | |
| } else { | |
| l.Tail.Next = n | |
| } | |
| l.Tail = n | |
| l.Count++ | |
| } | |
| func (l *LinkedList[T]) RemoveTail() { | |
| if l.Count == 0 { | |
| return | |
| } | |
| if l.Count == 1 { | |
| l.Head = nil | |
| l.Tail = nil | |
| } else { | |
| node := l.TraverseUntil(func(n *Node[T]) bool { | |
| return n.Next == l.Tail | |
| }) | |
| node.Next = nil | |
| l.Tail = node | |
| } | |
| l.Count-- | |
| } | |
| func (l *LinkedList[T]) TraverseUntil(pred func(n *Node[T]) bool) *Node[T] { | |
| current := l.Head | |
| for !pred(current) { | |
| current = current.Next | |
| } | |
| return current | |
| } | |
| func (l *LinkedList[T]) Print() { | |
| fmt.Printf("%d: ", l.Count) | |
| print(l.Head) | |
| } | |
| func print[T any](node *Node[T]) { | |
| for node != nil { | |
| fmt.Printf("%v --> ", node.Value) | |
| node = node.Next | |
| } | |
| fmt.Println() | |
| } | |
| func main() { | |
| tail := Node[int]{Value: 4} | |
| scnd := Node[int]{Value: 3, Next: &tail} | |
| frst := Node[int]{Value: 2, Next: &scnd} | |
| head := Node[int]{Value: 1, Next: &frst} | |
| //print(&head) | |
| // swap frst & scnd | |
| frst.Next = &tail | |
| scnd.Next = &frst | |
| head.Next = &scnd | |
| //print(&head) | |
| fmt.Println("Adding to Head") | |
| l := LinkedList[int]{} | |
| l.AddHead(&Node[int]{Value: 4}) | |
| l.Print() | |
| l.AddHead(&Node[int]{Value: 3}) | |
| l.Print() | |
| l.AddHead(&Node[int]{Value: 2}) | |
| l.Print() | |
| l.AddHead(&Node[int]{Value: 1}) | |
| l.Print() | |
| fmt.Println() | |
| fmt.Println("Adding to Tail") | |
| l2 := LinkedList[int]{} | |
| l2.AddTail(&Node[int]{Value: 1}) | |
| l2.Print() | |
| l2.AddTail(&Node[int]{Value: 2}) | |
| l2.Print() | |
| l2.AddTail(&Node[int]{Value: 3}) | |
| l2.Print() | |
| l2.AddTail(&Node[int]{Value: 4}) | |
| l2.Print() | |
| fmt.Println() | |
| fmt.Println("Removing from Head") | |
| l.Print() | |
| l.RemoveHead() | |
| l.Print() | |
| l.RemoveHead() | |
| l.Print() | |
| l.RemoveHead() | |
| l.Print() | |
| l.RemoveHead() | |
| l.Print() | |
| fmt.Println() | |
| fmt.Println("Removing from Tail") | |
| l2.Print() | |
| l2.RemoveTail() | |
| l2.Print() | |
| l2.RemoveTail() | |
| l2.Print() | |
| l2.RemoveTail() | |
| l2.Print() | |
| l2.RemoveTail() | |
| l2.Print() | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment