GoLinkedList

package LinkedList

import (
    "errors"
    "fmt"
    "strings"
)

type Node struct {
    value interface{}
    next  *Node
}

type LinkedList struct {
    first *Node
    last  *Node
    size  int
}

func New(values ...interface{}) *LinkedList {
    ll := &LinkedList{}
    if len(values) > 0 {
        ll.Add(values...)
    }
    return ll
}

func (ll *LinkedList) Add(values ...interface{}) {
    for _, value := range values {
        node := &Node{value: value, next: nil}
        if ll.size == 0 {
            ll.first = node
            ll.last = node
        } else {
            ll.last.next = node
            ll.last = node
        }
        ll.size++
    }
}

func (ll *LinkedList) Append(values ...interface{}) {
    ll.Add(values...)
}

func (ll *LinkedList) Prepend(values ...interface{}) {
    for index := len(values) - 1; index >= 0; index-- {
        node := &Node{value: values[index], next: ll.first}
        ll.first = node
        if ll.size == 0 {
            ll.last = node
        }
        ll.size++
    }
}

func (ll *LinkedList) Set(index int, value interface{}) error {
    if !ll.withinRange(index) {
        return errors.New(fmt.Sprintf("LinkedList: index %d is out of range (size = %d)", index, ll.size))
    }

    foundValue := ll.first
    for i := 0; i != index; i++ {
        foundValue = foundValue.next
    }
    foundValue.value = value
    return nil
}

func (ll *LinkedList) Get(index int) (interface{}, error) {
    if !ll.withinRange(index) {
        return nil, errors.New(fmt.Sprintf("LinkedList: index %d is out of range (size = %d)", index, ll.size))
    }

    node := ll.first
    for i := 0; i != index; i, node = i+1, node.next {
    }
    return node.value, nil
}

func (ll *LinkedList) Remove(index int) error {
    if !ll.withinRange(index) {
        return errors.New(fmt.Sprintf("LinkedList: index %d is out of range (size = %d)", index, ll.size))
    } else if ll.size == 1 {
        ll.Clear()
    }

    var beforeNode *Node
    node := ll.first
    for e := 0; e != index; e, node, beforeNode = e+1, node.next, node {
    }

    if node == ll.first {
        ll.first = node.next
    }
    if node == ll.last {
        ll.last = beforeNode
    }
    if beforeNode != nil {
        beforeNode.next = node.next
    }

    node = nil
    ll.size--
    return nil
}

func (ll *LinkedList) Insert(index int, values ...interface{}) error {

    if !ll.withinRange(index) {
        return errors.New(fmt.Sprintf("LinkedList: index %d is out of range (size = %d)", index, ll.size))
    }
    if index == 0 {
        ll.Prepend(values...)
        return nil
    }

    ll.size += len(values)
    var beforeNode *Node
    foundNode := ll.first
    for e := 0; e != index; e, foundNode, beforeNode = e+1, foundNode.next, foundNode {
    }

    oldNextElement := beforeNode.next
    for _, value := range values {
        newElement := &Node{value: value}
        beforeNode.next = newElement
        beforeNode = newElement
    }
    beforeNode.next = oldNextElement
    return nil
}

func (ll *LinkedList) Contains(values ...interface{}) bool {
    valueMap := make(map[interface{}]bool)

    // заполняем map значениями
    for i := 0; i < len(values); i++ {
        valueMap[values[i]] = true
    }

    // проверяем каждый узел списка на наличие в map
    for node := ll.first; node != nil; node = node.next {
        if _, ok := valueMap[node.value]; ok {
            delete(valueMap, node.value)
        }

        if len(valueMap) == 0 {
            return true
        }
    }
    return false
}

func (ll *LinkedList) IndexOf(value interface{}) (int, error) {
    if ll.size == 0 {
        return -1, errors.New(fmt.Sprintf("LinkedList: list is empty (size = %d)", ll.size))
    }
    for index, node := range ll.Values() {
        if node == value {
            return index, nil
        }
    }
    return -1, errors.New(fmt.Sprintf("LinkedList: value %v is not in list", value))
}

func (ll *LinkedList) Empty() bool {
    return ll.size == 0
}

func (ll *LinkedList) Size() int {
    return ll.size
}

func (ll *LinkedList) Clear() {
    ll.first = nil
    ll.last = nil
    ll.size = 0
}

func (ll *LinkedList) Values() []interface{} {
    values := make([]interface{}, ll.size, ll.size)
    for v, node := 0, ll.first; node != nil; v, node = v+1, node.next {
        values[v] = node.value
    }
    return values
}

func (ll *LinkedList) Swap(i, j int) error {
    if !ll.withinRange(i) || !ll.withinRange(j) {
        return errors.New(fmt.Sprintf("LinkedList: i=%d or j=%d is out of range (size=%d)", i, j, ll.size))
    }
    if i == j {
        return nil
    }

    var node1, node2 *Node
    for e, currNode := 0, ll.first; node1 == nil || node2 == nil; e, currNode = e+1, currNode.next {
        switch e {
        case i:
            node1 = currNode
        case j:
            node2 = currNode
        }
    }
    node1.value, node2.value = node2.value, node1.value
    return nil
}

func (ll *LinkedList) Sort(less func(a, b interface{}) bool) {
    // Если список пустой или содержит только один элемент, он уже отсортирован.
    if ll.first == nil || ll.first.next == nil {
        return
    }

    // Создаем новый список, в который будем вставлять элементы в отсортированном порядке.
    sorted := &LinkedList{first: nil, last: nil, size: ll.size}

    // Перебираем все элементы и вставляем их в отсортированный список.
    for node := ll.first; node != nil; {
        next := node.next

        // Находим место, куда нужно вставить текущий элемент в отсортированный список.
        curr := sorted.first
        var prev *Node
        for curr != nil && less(curr.value, node.value) {
            prev = curr
            curr = curr.next
        }

        // Вставляем текущий элемент в отсортированный список.
        if prev == nil {
            sorted.first = node
        } else {
            prev.next = node
        }
        node.next = curr

        // Переходим к следующему элементу.
        node = next
    }

    // Обновляем первый и последний элементы в исходном списке.
    ll.first = sorted.first
    ll.last = sorted.last
}

func (ll *LinkedList) String() string {
    s := "LinkedList: ["
    strValues := make([]string, ll.size)
    for index, node := 0, ll.first; node != nil; index, node = index+1, node.next {
        strValues[index] = fmt.Sprintf("%v", node.value)
    }
    return s + strings.Join(strValues, ", ") + "]"
}

func (ll *LinkedList) withinRange(index int) bool {
    return 0 <= index && index < ll.size
}