singly_linked_list.go

package singly_linked_list

import (
	"bytes"
	"errors"
	"fmt"
)

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

type sList struct {
	head *sListNode
}

func (l *sList) IsEmpty() bool {
	return l.head == nil
}

func (l *sList) String() string {
	var buf bytes.Buffer

	buf.WriteString("[")

	for n := l.head; n != nil; n = n.next {
		s := fmt.Sprintf("%v", n.value)
		buf.WriteString(s)

		if n.next != nil {
			buf.WriteString(", ")
		}
	}

	buf.WriteString("]")

	return buf.String()
}

func (l *sList) Len() int {
	length := 0

	for n := l.head; n != nil; n = n.next {
		length++
	}

	return length
}

func (l *sList) Prepend(value interface{}) {
	l.head = &sListNode{value: value, next: l.head}
}

func (l *sList) PrependList(other *sList) {
	if other.IsEmpty() {
		return
	}

	other.Reverse()

	for cn := other.head; cn != nil; cn = cn.next {
		val := cn.value
		l.Prepend(val)
	}
}

// func (l *sList) Append(value interface{}) {}

// func (l *sList) AppendList(other *sList) {}

// func (l *sList) InsertAt(idx int, value interface{}) {}

// func (l *sList) InsertAfter(idx int, value interface{}) {}

func (l *sList) DeleteAt(idx int) error {
	if idx < 0 {
		return errors.New("index can't be negative")
	}

	if idx == 0 {
		if l.IsEmpty() {
			return errors.New("can not delete elements from empty list")
		}

		l.head = l.head.next
	}

	i := 0
	n := l.head
	p := n

	for i < idx {
		if n == nil {
			return fmt.Errorf("index %d is too big", idx)
		}

		p = n
		n = n.next

		i++
	}

	p.next = n.next

	return nil
}

func (l *sList) ForEach(f func(interface{})) {
	for n := l.head; n != nil; n = n.next {
		f(n.value)
	}
}

func (l *sList) Equal(other *sList) bool {
	if l.IsEmpty() && other.IsEmpty() {
		return true
	}

	if l.IsEmpty() || other.IsEmpty() {
		return false
	}

	h1, _ := l.Head()
	h2, _ := other.Head()

	if h1 == h2 {
		t1, _ := l.Tail()
		t2, _ := other.Tail()
		return t1.Equal(t2)
	}

	return false
}

func (l *sList) Reverse() {
	if l.IsEmpty() || l.head.next == nil {
		return
	}

	newList := New()
	thisList := l

	for {
		h, err := thisList.Head()

		if err != nil {
			break
		}

		newList.Prepend(h)

		thisList, _ = thisList.Tail()
	}

	l.head = newList.head
}

func (l *sList) Head() (interface{}, error) {
	if l.IsEmpty() {
		return nil, errors.New("can't get head of empty list")
	}

	return l.head.value, nil
}

func (l *sList) Tail() (*sList, error) {
	if l.IsEmpty() {
		return nil, errors.New("can't get tail of empty list")
	}

	return &sList{head: l.head.next}, nil
}

func (l *sList) Last() (interface{}, error) {
	if l.IsEmpty() {
		return nil, errors.New("can't get last element of empty list")
	}

	item := l.head

	for item.next != nil {
		item = item.next
	}

	return item.value, nil
}

func (l *sList) Get(idx int) (interface{}, error) {
	if l.IsEmpty() {
		return nil, errors.New("can't index an empty list")
	}

	if idx < 0 {
		return nil, errors.New("index can't be negative")
	}

	nextElem := l.head
	nextIdx := 0

	for nextElem != nil {
		if nextIdx == idx {
			return nextElem.value, nil
		}

		nextElem = nextElem.next
		nextIdx++
	}

	return nil, errors.New("index is too big")
}

func (l *sList) Clear() {
	l.head = nil
}

func New(s ...interface{}) *sList {
	l := &sList{}

	for i := range s {
		idx := len(s) - 1 - i
		l.Prepend(s[idx])
	}

	return l
}

singly_linked_list_test.go

package singly_linked_list

import (
	"bytes"
	"testing"
)

func TestIsEmpty(t *testing.T) {
	l := New()

	if !l.IsEmpty() {
		t.Error("should return true on empty list")
	}

	l.Prepend(true)

	if l.IsEmpty() {
		t.Error("should return false on non-empty list")
	}
}

func TestPrepend(t *testing.T) {
	l := New()

	l.Prepend(true)

	if expected := New(true); !l.Equal(expected) {
		t.Errorf("expected %v to be equal to %v", l, expected)
	}

	l.Prepend(42)

	if expected := New(42, true); !l.Equal(expected) {
		t.Errorf("expected %v to be equal to %v", l, expected)
	}
}

func TestGet(t *testing.T) {
	l := New(0, 1, 2, 3, 4)

	for idx := 0; idx <= 4; idx++ {
		val, err := l.Get(idx)

		if err != nil {
			t.Error(err)
		}

		if item := val.(int); item != idx {
			t.Errorf("%d != %d", item, idx)
		}
	}
}

func TestLen(t *testing.T) {
	l := New()

	if l.Len() != 0 {
		t.Error("empty list should have length of 0")
	}

	for idx := 1; idx <= 5; idx++ {
		l.Prepend(true)
		if length := l.Len(); length != idx {
			t.Errorf("%v != %d", length, idx)
		}
	}
}

func TestClear(t *testing.T) {
	l := New(true, false)

	if l.IsEmpty() {
		t.Error("should not be empty")
	}

	l.Clear()

	if !l.IsEmpty() {
		t.Error("should be cleared")
	}
}

func TestHeadOfEmptyList(t *testing.T) {
	l := New()

	_, err := l.Head()

	if err == nil {
		t.Error("should return error for empty list")
	}
}

func TestHeadOfNonEmptyList(t *testing.T) {
	l := New(84)

	elem, err := l.Head()

	if err != nil {
		t.Error("should not return error for non-empty list")
	}

	if el := elem.(int); el != 84 {
		t.Error("wrong element")
	}
}

func TestNewWithArguments(t *testing.T) {
	l := New(0, 1, 2, 3, 4, 5)

	for i := 0; i <= 5; i++ {
		el, err := l.Get(i)

		if err != nil {
			t.Error(err)
		}

		value := el.(int)

		if value != i {
			t.Errorf("%d != %d", value, i)
		}
	}
}

func TestString(t *testing.T) {
	if New().String() != "[]" {
		t.Error("should be '[]' for empty list")
	}

	if s := New(0).String(); s != "[0]" {
		t.Errorf("%s != %s", s, "[0]")
	}

	if s := New(0, 1).String(); s != "[0, 1]" {
		t.Errorf("%s != %s", s, "[0, 1]")
	}

	if s := New(true, false).String(); s != "[true, false]" {
		t.Errorf("%s != %s", s, "[true, false]")
	}
}

func TestTail(t *testing.T) {
	full := New(1, 2, 3, 4)

	tail, err := full.Tail()

	if err != nil {
		t.Error(err)
	}

	if expected := New(2, 3, 4); !tail.Equal(expected) {
		t.Errorf("expected %v to be equal to %v", tail, expected)
	}
}

func TestTailOfEmptyList(t *testing.T) {
	l := New()

	tail, err := l.Tail()

	if tail != nil {
		t.Error("should return nil")
	}

	if err == nil {
		t.Error("should return error")
	}
}

func TestTailOfOneElementList(t *testing.T) {
	l := New(1)

	tail, err := l.Tail()

	if err != nil {
		t.Error(err)
	}

	if !tail.IsEmpty() {
		t.Error("should be empty")
	}
}

func TestLastOfEmptyList(t *testing.T) {
	l := New()

	_, err := l.Last()

	if err == nil {
		t.Error("should return error on empty list")
	}
}

func TestLastOfNonEmptyList(t *testing.T) {
	l := New(1, 2, 3)

	elem, err := l.Last()

	if err != nil {
		t.Error("should not return error on non-empty list")
	}

	if e := elem.(int); e != 3 {
		t.Errorf("%d != %d", e, 3)
	}
}

func TestReverseEmptyList(t *testing.T) {
	l := New()
	l.Reverse()

	if !l.IsEmpty() {
		t.Error("empty list is it's own reverse")
	}
}

func TestReverseOneElementList(t *testing.T) {
	l := New(1)
	l.Reverse()

	firstItem, _ := l.Get(0)

	if l.Len() != 1 || firstItem.(int) != 1 {
		t.Error("singleton list is it's own reverse")
	}
}

func TestReverseLongList(t *testing.T) {
	l := New(9, 8, 7, 6, 5, 4, 3, 2, 1, 0)
	l.Reverse()
	expected := New(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
	if !l.Equal(expected) {
		t.Errorf("expected %v to be equal to %v", l, expected)
	}
}

func TestEmptyListsEquality(t *testing.T) {
	l1 := New()
	l2 := New()

	if !l1.Equal(l2) {
		t.Errorf("%v != %v", l1, l2)
	}
}

func TestNonEmptyListsEquality(t *testing.T) {
	l1 := New(1, 2, 3, 4, 5)
	l2 := New(1, 2, 3, 4, 5)
	l3 := New(1, 2, 3, 3, 5)
	l4 := New()

	if !l1.Equal(l2) {
		t.Errorf("%v should be equal to  %v", l1, l2)
	}

	if l1.Equal(l3) {
		t.Errorf("%v should not be equal to  %v", l1, l2)
	}

	if l1.Equal(l4) {
		t.Errorf("%v should not be equal to  %v", l1, l2)
	}
}

func TestPrependList(t *testing.T) {
	l := New(42, 98)
	other := New(93, 52)

	l.PrependList(other)

	expected := New(93, 52, 42, 98)

	if !l.Equal(expected) {
		t.Errorf("expected %v to be equal to %v", l, expected)
	}
}

func TestForEachEmptyList(t *testing.T) {
	New().ForEach(func(item interface{}) {
		t.Error("execution must not get here")
	})
}

func TestForEachNonEmptyList(t *testing.T) {
	l := New("a", "b", "c", "d")

	var acc bytes.Buffer

	l.ForEach(func(item interface{}) {
		acc.WriteString(item.(string))
	})

	expected := "abcd"

	if actual := acc.String(); actual != expected {
		t.Errorf("%#v != %#v", actual, expected)
	}
}

func TestDeleteAtBeginning(t *testing.T) {
	l := New(1, 2, 3)

	err := l.DeleteAt(0)

	if err != nil {
		t.Error(err)
	}

	expected := New(2, 3)

	if !l.Equal(expected) {
		t.Errorf("%v != %v", l, expected)
	}
}

func TestDeleteAtMiddle(t *testing.T) {
	l := New(1, 2, 3)

	err := l.DeleteAt(1)

	if err != nil {
		t.Error(err)
	}

	expected := New(1, 3)

	if !l.Equal(expected) {
		t.Errorf("%v != %v", l, expected)
	}
}

func TestDeleteAtEnd(t *testing.T) {
	l := New(1, 2, 3)

	err := l.DeleteAt(2)

	if err != nil {
		t.Error(err)
	}

	expected := New(1, 2)

	if !l.Equal(expected) {
		t.Errorf("%v != %v", l, expected)
	}
}

func TestDeleteAtNegativeIndex(t *testing.T) {
	l := New(1, 2, 3)

	err := l.DeleteAt(-8)

	if err == nil {
		t.Error("should return error")
	}

	expected := New(1, 2, 3)

	if !l.Equal(expected) {
		t.Errorf("%v != %v", l, expected)
	}
}

func TestDeleteAtBeyondLast(t *testing.T) {
	l := New(1, 2, 3)

	err := l.DeleteAt(8)

	if err == nil {
		t.Error("should return error")
	}

	expected := New(1, 2, 3)

	if !l.Equal(expected) {
		t.Errorf("%v != %v", l, expected)
	}
}