双向链表

[lsyf]

1. 需求

• 链表

2. 设计

• 结构
  1. 双向链表，头节点，尾节点和长度；节点，数据和前后节点指针（代码）
  2. 方案二：双向链表，root和len。root.pre为tail，tail.next为root
• 行为
  1. 新增、删除、打印、获取、清空、包含
• 边界条件
  1. 链表为空时新增
  2. 链表只有一个节点时删除
  3. 插入到头部

3. 代码

package list

import (
	"fmt"
	"strings"
)

type Node struct {
	next, pre *Node
	Value     interface{}
}

type LinkedList struct {
	root, tail *Node
	len        int
}

func NewLinkedList() *LinkedList {
	l := new(LinkedList)
	return l
}

func (l *LinkedList) Add(v interface{}) {
	if l.root == nil {
		l.root = &Node{Value: v}
		l.tail = l.root
		l.len++
		return
	}

	n := &Node{Value: v}
	n.pre = l.tail
	l.tail.next = n
	l.tail = n
	l.len++
}

func (l *LinkedList) Get(i int) interface{} {
	if i < 0 || i >= l.len {
		return nil
	}

	switch {
	case i == 0:
		return l.root.Value
	case i == l.len-1:
		return l.tail.Value
	case i < l.len/2: //下标小于长度1/2从头结点遍历
		n := l.root
		for x := 0; x < i-1; x++ {
			n = n.next
		}
		return n.Value
	default: //下标大于长度1/2从尾结点遍历
		n := l.tail
		for x := 0; x < l.len-1-i; x++ {
			n = n.pre
		}
		return n.Value
	}
}

func (l *LinkedList) Remove(i int) interface{} {
	if i < 0 || i >= l.len {
		return nil
	}

	switch {
	case l.len == 1: //长度为1代表只有头结点可删除
		n := l.root
		l.root = nil
		l.tail = nil
		l.len--
		return n.Value
	case i == 0:
		n := l.root
		l.root = l.root.next
		l.root.pre = nil
		l.len--
		return n.Value
	case i == l.len-1:
		n := l.tail
		l.tail = l.tail.pre
		l.tail.next = nil
		l.len--
		return n.Value
	case i < l.len/2: //下标小于长度1/2从头结点遍历
		n := l.root
		for x := 0; x < i-1; x++ {
			n = n.next
		}
		n.pre.next = n.next
		n.next.pre = n.pre
		l.len--
		return n.Value
	default: //下标大于长度1/2从尾结点遍历
		n := l.tail
		for x := 0; x < l.len-1-i; x++ {
			n = n.pre
		}
		n.pre.next = n.next
		n.next.pre = n.pre
		l.len--
		return n.Value
	}
}

func (l *LinkedList) Clear() {
	l.root = nil
	l.tail = nil
	l.len = 0
}
func (l *LinkedList) Contains(v interface{}) bool {
	n := l.root
	for n != nil {
		if n.Value == v {
			return true
		}
		n = n.next
	}
	return false
}

func (l *LinkedList) String() (str string) {
	data := make([]string, 0, l.len)
	n := l.root
	for n != nil {
		data = append(data, fmt.Sprintf("%v", n.Value))
		n = n.next
	}
	str = strings.Join(data, ",")
	str = "[" + str + "]"
	return
}