123 lines
1.9 KiB
Go
123 lines
1.9 KiB
Go
package ds
|
|
|
|
import "fmt"
|
|
|
|
type LinkedList[T any] struct {
|
|
head *linkedListNode[T]
|
|
tail *linkedListNode[T]
|
|
length int
|
|
}
|
|
|
|
var _ List[int] = &LinkedList[int]{}
|
|
|
|
func NewLinkedList[T any]() *LinkedList[T] {
|
|
return &LinkedList[T]{}
|
|
}
|
|
|
|
func (l *LinkedList[T]) Add(value T) {
|
|
if l.length == 0 {
|
|
l.head = &linkedListNode[T]{value: value}
|
|
l.tail = l.head
|
|
l.length++
|
|
return
|
|
}
|
|
|
|
newNode := &linkedListNode[T]{
|
|
value: value,
|
|
prev: l.tail,
|
|
}
|
|
l.tail.next = newNode
|
|
l.tail = newNode
|
|
l.length++
|
|
}
|
|
|
|
func (l *LinkedList[T]) AddAll(values Iterable[T]) {
|
|
values.Each(l.Add)
|
|
}
|
|
|
|
func (l *LinkedList[T]) Get(index int) T {
|
|
return l.getNode(index).value
|
|
}
|
|
|
|
func (l *LinkedList[T]) Set(index int, value T) {
|
|
l.getNode(index).value = value
|
|
}
|
|
|
|
func (l *LinkedList[T]) RemoveAt(index int) T {
|
|
node := l.getNode(index)
|
|
|
|
if node.prev != nil {
|
|
node.prev.next = node.next
|
|
} else {
|
|
l.head = node.next
|
|
}
|
|
|
|
if node.next != nil {
|
|
node.next.prev = node.prev
|
|
} else {
|
|
l.tail = node.prev
|
|
}
|
|
|
|
l.length--
|
|
return node.value
|
|
}
|
|
|
|
func (l *LinkedList[T]) Clear() {
|
|
l.head = nil
|
|
l.tail = nil
|
|
l.length = 0
|
|
}
|
|
|
|
func (l *LinkedList[T]) Each(f func(value T)) {
|
|
node := l.head
|
|
for node != nil {
|
|
f(node.value)
|
|
node = node.next
|
|
}
|
|
}
|
|
|
|
func (l *LinkedList[T]) Size() int {
|
|
return l.length
|
|
}
|
|
|
|
func (l *LinkedList[T]) Empty() bool {
|
|
return l.Size() == 0
|
|
}
|
|
|
|
func (l *LinkedList[T]) getNode(index int) *linkedListNode[T] {
|
|
if index < 0 || index > l.length {
|
|
panic(fmt.Sprintf("invalid index %d for list with size %d", index, l.Size()))
|
|
}
|
|
|
|
if index == 0 {
|
|
return l.head
|
|
}
|
|
|
|
if index == l.length-1 {
|
|
return l.tail
|
|
}
|
|
|
|
if index > l.length/2 {
|
|
index = l.length - index
|
|
node := l.tail
|
|
for index > 0 {
|
|
node = node.prev
|
|
index--
|
|
}
|
|
return node
|
|
}
|
|
|
|
node := l.head
|
|
for index > 0 {
|
|
node = node.next
|
|
index--
|
|
}
|
|
return node
|
|
}
|
|
|
|
type linkedListNode[T any] struct {
|
|
value T
|
|
next *linkedListNode[T]
|
|
prev *linkedListNode[T]
|
|
}
|