linked_list.go

package main

import (
	"fmt"
)

type Node struct {
	Data interface{}
	Prev *Node
	Next *Node
}

type List struct {
	head *Node
	tail *Node
}

func NewList(items ...interface{}) *List {
	list := &List{
		head: &Node{nil, nil, nil},
		tail: &Node{nil, nil, nil},
	}
	list.head.Next = list.tail
	list.tail.Prev = list.head
	for _, item := range items {
		list.PushToBack(item)
	}
	return list
}

func (l *List) PushToFront(data interface{}) {
	node := &Node{data, nil, nil}
	node.Prev = l.head
	node.Next = l.head.Next
	l.head.Next.Prev = node
	l.head.Next = node
}

func (l *List) PushToBack(data interface{}) {
	node := &Node{data, nil, nil}
	node.Prev = l.tail.Prev
	node.Next = l.tail
	l.tail.Prev.Next = node
	l.tail.Prev = node
}

func (l *List) Remove(node *Node) {
	if node == nil {
		return
	}
	node.Prev.Next = node.Next
	node.Next.Prev = node.Prev
}

func (l *List) MoveToFront(node *Node) {
	if node == nil {
		return
	}
	l.Remove(node)
	l.PushToFront(node.Data)
}

func (l *List) MoveToBack(node *Node) {
	if node == nil {
		return
	}
	l.Remove(node)
	l.PushToBack(node.Data)
}

func (l *List) Back() *Node {
	if l.tail.Prev == l.head {
		return nil
	}
	return l.tail.Prev
}

func (l *List) Front() *Node {
	if l.tail.Prev == l.head {
		return nil
	}
	return l.head.Next
}

func (l *List) Search(target interface{}) *Node {
	current := l.head.Next
	for current != l.tail {
		if current.Data == target {
			return current
		}
		current = current.Next
	}
	return nil
}

func (l *List) Reverse() {
	i := l.head.Next
	j := l.tail.Prev
	for i != l.tail && j != l.head && i != j && i.Prev != j {
		i.Data, j.Data = j.Data, i.Data
		i = i.Next
		j = j.Prev
	}
}

func (l *List) String() string {
	ans := ""
	current := l.head.Next
	for current != l.tail {
		if len(ans) != 0 {
			ans += " "
		}
		ans += fmt.Sprintf("%v", current.Data)
		current = current.Next
	}
	return fmt.Sprintf("List(%s)", ans)
}

func (l *List) IsEmpty() bool {
	return l.head.Next == l.tail
}

func main() {
	list := NewList(1, 2, 3)
	fmt.Println(list)

	list.PushToBack(4)
	fmt.Println(list)

	list.PushToFront(0)
	fmt.Println(list)

	list.MoveToBack(list.Front())
	fmt.Println(list)

	list.MoveToFront(list.Back())
	fmt.Println(list)

	node := list.Search(2)
	if node != nil {
		fmt.Println("Node data:", node.Data)
		list.Remove(node)
		fmt.Println(list)
	}

	list.Reverse()
	fmt.Println(list)

	for !list.IsEmpty() {
		list.Remove(list.Front())
	}
	fmt.Println(list)

	list.PushToFront(0)
	fmt.Println(list)

	fmt.Println("OK")
}