By Golang

  1. // Package linkedlist creates a ItemLinkedList data structure for the Item type
  2. package linkedlist
  4. import (
  5.     "fmt"
  6.     "sync"
  7. )
  9. // Item the type of the linked list
  10. type Item interface{}
  12. // Node a single node that composes the list
  13. type Node struct {
  14.     content Item
  15.     next    *Node
  16. }
  18. // ItemLinkedList the linked list of Items
  19. type ItemLinkedList struct {
  20.     head *Node
  21.     size int
  22.     lock sync.RWMutex
  23. }
  25. // Append adds an Item to the end of the linked list
  26. func (ll *ItemLinkedList) Append(t Item) {
  27.     ll.lock.Lock()
  28.     node := Node{t, nil}
  29.     if ll.head == nil {
  30.         ll.head = &node
  31.     } else {
  32.         last := ll.head
  33.         for {
  34.             if last.next == nil {
  35.                 break
  36.             }
  37.             last = last.next
  38.         }
  39.         last.next = &node
  40.     }
  41.     ll.size++
  42.     ll.lock.Unlock()
  43. }
  45. // Insert adds an Item at position i
  46. func (ll *ItemLinkedList) Insert(i int, t Item) error {
  47.     ll.lock.Lock()
  48.     defer ll.lock.Unlock()
  49.     if i < 0 || i > ll.size {
  50.         return fmt.Errorf("Index out of bounds")
  51.     }
  52.     addNode := Node{t, nil}
  53.     if i == 0 {
  54.         addNode.next = ll.head
  55.         ll.head = &addNode
  56.         return nil
  57.     }
  58.     node := ll.head
  59.     j := 0
  60.     for j < i-2 {
  61.         j++
  62.         node = node.next
  63.     }
  64.     addNode.next = node.next
  65.     node.next = &addNode
  66.     ll.size++
  67.     return nil
  68. }
  70. // RemoveAt removes a node at position i
  71. func (ll *ItemLinkedList) RemoveAt(i int) (*Item, error) {
  72.     ll.lock.Lock()
  73.     defer ll.lock.Unlock()
  74.     if i < 0 || i > ll.size {
  75.         return nil, fmt.Errorf("Index out of bounds")
  76.     }
  77.     node := ll.head
  78.     j := 0
  79.     for j < i-1 {
  80.         j++
  81.         node = node.next
  82.     }
  83.     remove := node.next
  84.     node.next = remove.next
  85.     ll.size--
  86.     return &remove.content, nil
  87. }
  89. // IndexOf returns the position of the Item t
  90. func (ll *ItemLinkedList) IndexOf(t Item) int {
  91.     ll.lock.RLock()
  92.     defer ll.lock.RUnlock()
  93.     node := ll.head
  94.     j := 0
  95.     for {
  96.         if node.content == t {
  97.             return j
  98.         }
  99.         if node.next == nil {
  100.             return -1
  101.         }
  102.         node = node.next
  103.         j++
  104.     }
  105. }
  107. // IsEmpty returns true if the list is empty
  108. func (ll *ItemLinkedList) IsEmpty() bool {
  109.     ll.lock.RLock()
  110.     defer ll.lock.RUnlock()
  111.     if ll.head == nil {
  112.         return true
  113.     }
  114.     return false
  115. }
  117. // Size returns the linked list size
  118. func (ll *ItemLinkedList) Size() int {
  119.     ll.lock.RLock()
  120.     defer ll.lock.RUnlock()
  121.     size := 1
  122.     last := ll.head
  123.     for {
  124.         if last == nil || last.next == nil {
  125.             break
  126.         }
  127.         last = last.next
  128.         size++
  129.     }
  130.     return size
  131. }
  133. // Insert adds an Item at position i
  134. func (ll *ItemLinkedList) String() {
  135.     ll.lock.RLock()
  136.     defer ll.lock.RUnlock()
  137.     node := ll.head
  138.     j := 0
  139.     for {
  140.         if node == nil {
  141.             break
  142.         }
  143.         j++
  144.         fmt.Print(node.content)
  145.         fmt.Print(" ")
  146.         node = node.next
  147.     }
  148.     fmt.Println()
  149. }
  151. // Head returns a pointer to the first node of the list
  152. func (ll *ItemLinkedList) Head() *Node {
  153.     ll.lock.RLock()
  154.     defer ll.lock.RUnlock()
  155.     return ll.head
  156. }