Golang 双向链表

模拟的 java LinkedList，还可以实现双向链表的一些功能，比如，插入头节点、插入尾节点、删除头节点、删除尾节点等等…

type LinkedList struct {
	len  int
	head *LinkedNode
	tail *LinkedNode
}

type LinkedNode struct {
	data int
	next *LinkedNode
	pre  *LinkedNode
}

func NewLinkedList() *LinkedList {
	return &LinkedList{
		len:  0,
		head: nil,
		tail: nil,
	}
}

func (l *LinkedList) add(data int) {

	node := &LinkedNode{
		data: data,
	}

	if l.head == nil {
		l.head = node
		l.tail = node
	} else {
		current := l.tail
		current.next = node
		node.pre = current

		l.tail = node
	}
	l.len++
}

func (l *LinkedList) size() int {
	return l.len
}

func (l *LinkedList) print() {
	head := l.head
	for head != nil {
		fmt.Printf("%d ", head.data)
		head = head.next
	}
	fmt.Println()
}

func main() {

	list := NewLinkedList()
	list.add(20)
	list.add(30)
	list.add(40)

	list.remove(30)
	list.print()

	list.add(50)
	list.print()

	list.remove(20)
	list.print()

	list.addHead(-100)
	list.print()

	list.addLast(100)
	list.print()

	fmt.Println(list.size())
}

今天把删除元素的功能添加了

func (l *LinkedList) remove(data int) {

	if l.head == nil {
		return
	}

	if l.head.data == data {
		h := l.head.next
		h.pre = nil
		l.head = h
		l.len--
	} else if l.tail.data   == data {
		p := l.tail.pre
		p.next = nil
		l.tail = p
		l.len--
	}

	head := l.head
	for head != nil {
		if head.data == data {
			p := head.pre
			n := head.next
			n.pre = p
			p.next = n
			l.len--
			return
		}
		head = head.next
	}
}

今天添加插入头节点、尾节点功能

func (l *LinkedList) addHead(data int) {

	node := &LinkedNode{
		data: data,
	}

	if l.head != nil {
		next := l.head
		next.pre = node
		node.next = next
		l.head = node
	} else {
		l.head = node
		l.tail = node
	}
	l.len++
}

func (l *LinkedList) addLast(data int) {

	node := &LinkedNode{
		data: data,
	}

	if l.tail != nil {
		last :=  l.tail
		last.next = node
		node.pre = last
	} else {
		l.head = node
		l.tail = node
	}
	l.len++
}