• By Golang

    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. }