doublyLinklist
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153
package main
import (
"fmt"
)
type Node struct {
value int
next *Node
prev *Node
}
func NewNode(val int) Node {
return Node{value: val, next : nil, prev : nil}
}
type MyDoubleLinklist struct{
head *Node
tail *Node
length int
}
func NewMyDoubleLinklist(value int) MyDoubleLinklist {
newNode := NewNode(value)
return MyDoubleLinklist{ head: &newNode, tail: &newNode, length: 1}
}
func (list *MyDoubleLinklist) append(value int) MyDoubleLinklist {
newNode := NewNode(value)
list.tail.next = &newNode
newNode.prev = list.tail
list.tail = &newNode
list.length++
return *list
}
func (list *MyDoubleLinklist) prepend(value int) MyDoubleLinklist {
newNode := NewNode(value)
newNode.next = list.head
list.head.prev = &newNode
list.head = &newNode
list.length++
return *list
}
func (list *MyDoubleLinklist) insert(index, value int) (MyDoubleLinklist, error) {
if index < 0 || index > list.length {
return *list, fmt.Errorf("invalid input index should be in 0 and %d", list.length)
}
if index == 0 {
return list.prepend(value), nil
} else if index == list.length {
return list.append(value), nil
}
//get index node at index
indexNode := list.traverseToIndexNode(index)
newNode := NewNode(value)
prevNode := indexNode.prev
indexNode.prev = &newNode
prevNode.next = &newNode
newNode.prev = prevNode
newNode.next = indexNode
list.length++
return *list, nil
}
func (list *MyDoubleLinklist) remove(index int) (MyDoubleLinklist, error) {
if index < 0 || index > list.length {
return *list, fmt.Errorf("invalid input index should be in 0 and %d", list.length)
}
if index == 0 {
list.head.next = nil
list.head = list.head.next
return *list, nil
}
//get leader node
indexNode := list.traverseToIndexNode(index)
prevNode := indexNode.prev
nextNode := indexNode.next
fmt.Printf("\n remove node at %d , leader is : %v", index, indexNode)
prevNode.next = indexNode.next
nextNode.prev = indexNode.prev
return *list, nil
}
//return node at index
func(list *MyDoubleLinklist) traverseToIndexNode(index int) *Node {
idxNode := list.head
c := 0
for c < index {
idxNode = idxNode.next
c++
}
return idxNode
}
func(list *MyDoubleLinklist) print() {
head := list.head
for head != nil {
fmt.Printf("%d \t", head.value)
head = head.next
}
fmt.Println()
}
func(list *MyDoubleLinklist) printReverse() {
fmt.Println("reverseList: ")
tail := list.tail
for tail != nil {
fmt.Printf("%d \t", tail.value)
tail = tail.prev
}
fmt.Println()
}
func main() {
list := NewMyDoubleLinklist(5)
list.append(12)
list.append(10)
list.prepend(15)
list.prepend(1)
list.print()
list.printReverse()
_, err := list.remove(2)
if err != nil {
fmt.Println("insert error: ", err)
}
fmt.Println("\nafter remove node at index 2")
list.print()
list.printReverse()
_, err = list.insert(1, 100)
if err != nil {
fmt.Println("insert error: ", err)
}
fmt.Printf("\nafter insert node value %d at index %d \n", 100, 1)
list.print()
list.printReverse()
}
Go
INFO