list

Documentation

Index

• type LinkedList
  • func CreateLinkedList() *LinkedList
  • func (linkedList *LinkedList) Add(index int, value ...interface{}) error
  • func (linkedList *LinkedList) AddFirst(value ...interface{})
  • func (linkedList *LinkedList) AddLast(value ...interface{})
  • func (linkedList LinkedList) Contains(value interface{}) bool
  • func (linkedList *LinkedList) Foreach(foreachFunc func(index int, value interface{}) bool)
  • func (linkedList LinkedList) Get(index int) (interface{}, error)
  • func (linkedList LinkedList) GetFirst() (interface{}, error)
  • func (linkedList LinkedList) GetLast() (interface{}, error)
  • func (linkedList LinkedList) GetSize() int
  • func (linkedList LinkedList) IsEmpty() bool
  • func (linkedList *LinkedList) Iterator(iteratorFunc func(iterator common.Iterator) bool)
  • func (linkedList *LinkedList) Remove(index int) (interface{}, error)
  • func (linkedList *LinkedList) RemoveAllElement(value interface{}) int
  • func (linkedList *LinkedList) RemoveElement(value interface{})
  • func (linkedList *LinkedList) RemoveFirst() (interface{}, error)
  • func (linkedList *LinkedList) RemoveIfMatch(matchFunc func(value interface{}) bool) int
  • func (linkedList *LinkedList) RemoveLast() (interface{}, error)
  • func (linkedList *LinkedList) Set(index int, value interface{}) error
  • func (linkedList LinkedList) String() string
  • func (linkedList *LinkedList) ToSlice() []interface{}
• type LinkedListIterator
  • func (iterator LinkedListIterator) Get() (interface{}, error)
  • func (iterator *LinkedListIterator) Remove()
  • func (iterator LinkedListIterator) Set(value interface{}) error
• type List
• type LoopList
  • func CreateLoopList() *LoopList
  • func (loopList *LoopList) Add(index int, value ...interface{}) error
  • func (loopList *LoopList) AddFirst(value ...interface{})
  • func (loopList *LoopList) AddLast(value ...interface{})
  • func (loopList LoopList) Contains(value interface{}) bool
  • func (loopList *LoopList) Foreach(foreachFunc func(index int, value interface{}) bool)
  • func (loopList LoopList) Get(index int) (interface{}, error)
  • func (loopList LoopList) GetFirst() (interface{}, error)
  • func (loopList LoopList) GetLast() (interface{}, error)
  • func (loopList LoopList) GetSize() int
  • func (loopList LoopList) IsEmpty() bool
  • func (loopList *LoopList) Iterator(iteratorFunc func(iterator common.Iterator) bool)
  • func (loopList *LoopList) Remove(index int) (interface{}, error)
  • func (loopList *LoopList) RemoveAllElement(value interface{}) int
  • func (loopList *LoopList) RemoveElement(value interface{})
  • func (loopList *LoopList) RemoveFirst() (interface{}, error)
  • func (loopList *LoopList) RemoveIfMatch(matchFunc func(value interface{}) bool) int
  • func (loopList *LoopList) RemoveLast() (interface{}, error)
  • func (loopList *LoopList) Set(index int, value interface{}) error
  • func (loopList LoopList) String() string
  • func (loopList *LoopList) ToSlice() []interface{}
• type LoopListIterator
  • func (iterator LoopListIterator) Get() (interface{}, error)
  • func (iterator *LoopListIterator) Remove()
  • func (iterator LoopListIterator) Set(value interface{}) error
• type SkipList
  • func CreateSkipList() *SkipList
  • func (skipList *SkipList) Add(score int, data interface{})
  • func (skipList SkipList) Find(score int) (interface{}, bool)
  • func (skipList *SkipList) Remove(score int)

Types

type LinkedList

type LinkedList struct {
	// contains filtered or unexported fields
}

单项链表 单项链表的优势是节省存储空间

func CreateLinkedList

func CreateLinkedList() *LinkedList

创建单向链表

func (*LinkedList) Add

func (linkedList *LinkedList) Add(index int, value ...interface{}) error

 	O(n)
	在某个位置添加元素

func (*LinkedList) AddFirst

func (linkedList *LinkedList) AddFirst(value ...interface{})

O(len(value)) 在链表的头部添加元素

func (*LinkedList) AddLast

func (linkedList *LinkedList) AddLast(value ...interface{})

O(len(value)) 在链表的尾部添加元素

func (LinkedList) Contains

func (linkedList LinkedList) Contains(value interface{}) bool

O(n) 检查是否包含某一个元素值

func (*LinkedList) Foreach

func (linkedList *LinkedList) Foreach(foreachFunc func(index int, value interface{}) bool)

O(n) 对链表进行循环处理 func(value interface{}) bool bool 表示是否终止循环

func (LinkedList) Get

func (linkedList LinkedList) Get(index int) (interface{}, error)

O(n) 获取第index个元素

func (LinkedList) GetFirst

func (linkedList LinkedList) GetFirst() (interface{}, error)

O(1) 获取链表的第一个元素

func (LinkedList) GetLast

func (linkedList LinkedList) GetLast() (interface{}, error)

O(n) 获取链表的最后一个元素

func (LinkedList) GetSize

func (linkedList LinkedList) GetSize() int

获取链表的大小

func (LinkedList) IsEmpty

func (linkedList LinkedList) IsEmpty() bool

获取链表是否为空

func (*LinkedList) Iterator

func (linkedList *LinkedList) Iterator(iteratorFunc func(iterator common.Iterator) bool)

可以删除和设置节点值的迭代器

func (*LinkedList) Remove

func (linkedList *LinkedList) Remove(index int) (interface{}, error)

O(n) 删除第index位置的的元素

func (*LinkedList) RemoveAllElement

func (linkedList *LinkedList) RemoveAllElement(value interface{}) int

O(n) 删除所有节点值等于value的节点

func (*LinkedList) RemoveElement

func (linkedList *LinkedList) RemoveElement(value interface{})

O(n) 删除某个某个元素值

func (*LinkedList) RemoveFirst

func (linkedList *LinkedList) RemoveFirst() (interface{}, error)

O(1) 删除第一个元素

func (*LinkedList) RemoveIfMatch

func (linkedList *LinkedList) RemoveIfMatch(matchFunc func(value interface{}) bool) int

O(n) 根据条件删除节点

func (*LinkedList) RemoveLast

func (linkedList *LinkedList) RemoveLast() (interface{}, error)

O(n) 删除最后一个元素

func (*LinkedList) Set

func (linkedList *LinkedList) Set(index int, value interface{}) error

O(n) 设置元素的值

func (LinkedList) String

func (linkedList LinkedList) String() string

O(n) 字符串打印

func (*LinkedList) ToSlice

func (linkedList *LinkedList) ToSlice() []interface{}

将链表转换成切片

type LinkedListIterator

type LinkedListIterator struct {
	// contains filtered or unexported fields
}

linkedList迭代器,用于再遍历的过程中删除元素和修改元素

func (LinkedListIterator) Get

func (iterator LinkedListIterator) Get() (interface{}, error)

获取value

func (*LinkedListIterator) Remove

func (iterator *LinkedListIterator) Remove()

删除节点

func (LinkedListIterator) Set

func (iterator LinkedListIterator) Set(value interface{}) error

修改节点的值

type List

type List interface {
	fmt.Stringer

	common.SortAble

	GetSize() int

	IsEmpty() bool

	Add(index int, value ...interface{}) error

	AddFirst(value ...interface{})

	AddLast(value ...interface{})

	Get(index int) (interface{}, error)

	GetFirst() (interface{}, error)

	GetLast() (interface{}, error)

	Set(index int, value interface{}) error

	Remove(index int) (interface{}, error)

	RemoveFirst() (interface{}, error)

	RemoveLast() (interface{}, error)

	/*
		删除第一个为value的元素
	*/
	RemoveElement(value interface{})

	/*
		用于按条件删除元素
	*/
	RemoveIfMatch(matchFunc func(value interface{}) bool) int

	/*
		删除所有值为value的元素
	*/
	RemoveAllElement(value interface{}) int

	Contains(value interface{}) bool

	/*
		循环中按条件查找或按条件查找设置节点值的属性(存储的是指针类型修改属性才生效)
	*/
	Foreach(foreachFunc func(index int, value interface{}) bool)
}

列表接口

type LoopList

type LoopList struct {
	// contains filtered or unexported fields
}

循环双向链表 当只存在头节点,尾部节点,虚拟节点的时候: 头节点在虚拟节点之后 head = dummyNode.next, head.prev = dummyNode 尾部节点在虚拟节点之前 tail = dummyNode.prev, tail.next = dummyNode 尾部节点在头节点之后 head.next = tail, tail.prev = head 双向链表的优势是双端插入都是O(1)的时间复杂度,可用于构建双端队列

func CreateLoopList

func CreateLoopList() *LoopList

创建双向循环链表

func (*LoopList) Add

func (loopList *LoopList) Add(index int, value ...interface{}) error

O(n) 添加元素

func (*LoopList) AddFirst

func (loopList *LoopList) AddFirst(value ...interface{})

O(len(value)) 在头部添加元素

func (*LoopList) AddLast

func (loopList *LoopList) AddLast(value ...interface{})

O(len(value)) 在头部添加元素

func (LoopList) Contains

func (loopList LoopList) Contains(value interface{}) bool

检查是否包含某个元素

func (*LoopList) Foreach

func (loopList *LoopList) Foreach(foreachFunc func(index int, value interface{}) bool)

对链表进行循环

func (LoopList) Get

func (loopList LoopList) Get(index int) (interface{}, error)

O(n/2) 获取某个位置的元素

func (LoopList) GetFirst

func (loopList LoopList) GetFirst() (interface{}, error)

O(1)

func (LoopList) GetLast

func (loopList LoopList) GetLast() (interface{}, error)

O(1)

func (LoopList) GetSize

func (loopList LoopList) GetSize() int

获取链表的大小

func (LoopList) IsEmpty

func (loopList LoopList) IsEmpty() bool

获取链表是否为空 当虚拟节点的头部和尾部为空的时候，表示循环链表为空

func (*LoopList) Iterator

func (loopList *LoopList) Iterator(iteratorFunc func(iterator common.Iterator) bool)

可以删除和设置节点值的迭代器

func (*LoopList) Remove

func (loopList *LoopList) Remove(index int) (interface{}, error)

O(n/2) 根据索引删除节点

func (*LoopList) RemoveAllElement

func (loopList *LoopList) RemoveAllElement(value interface{}) int

删除值为value的全部元素

func (*LoopList) RemoveElement

func (loopList *LoopList) RemoveElement(value interface{})

根据元素值删除第一个元素

func (*LoopList) RemoveFirst

func (loopList *LoopList) RemoveFirst() (interface{}, error)

func (*LoopList) RemoveIfMatch

func (loopList *LoopList) RemoveIfMatch(matchFunc func(value interface{}) bool) int

根据条件删除元素

func (*LoopList) RemoveLast

func (loopList *LoopList) RemoveLast() (interface{}, error)

func (*LoopList) Set

func (loopList *LoopList) Set(index int, value interface{}) error

O(n/2) 设置某个索引的位置节点的值

func (LoopList) String

func (loopList LoopList) String() string

func (*LoopList) ToSlice

func (loopList *LoopList) ToSlice() []interface{}

type LoopListIterator

type LoopListIterator struct {
	// contains filtered or unexported fields
}

loopList迭代器,用于再遍历的过程中删除元素和修改元素

func (LoopListIterator) Get

func (iterator LoopListIterator) Get() (interface{}, error)

获取value

func (*LoopListIterator) Remove

func (iterator *LoopListIterator) Remove()

删除节点

func (LoopListIterator) Set

func (iterator LoopListIterator) Set(value interface{}) error

修改节点的值

type SkipList

type SkipList struct {
	// contains filtered or unexported fields
}

跳跃表的结构，可以用作纯内存的log(n)效率的索引结构。 和hashtable相比劣势会消耗更多的内存构建索引，查询效率不是O(1)。优势是支持按照分数以log(n)的效率进行范围检索。 和树结构相比插入删除操作简单效率高，不需要处理平衡问题。范围查询和排名查询不需要额外遍历操作，效率会高。 head-> 3-> tail

|			|	   |

head-> 2->3->4->tail

|		 |	|  |   |

head->1->2->3->4->tail

func CreateSkipList

func CreateSkipList() *SkipList

创建跳跃表

func (*SkipList) Add

func (skipList *SkipList) Add(score int, data interface{})

向跳跃表中添加数据,需要注意的是数据只存储在level=0的节点上，有利于节省空间

func (SkipList) Find

func (skipList SkipList) Find(score int) (interface{}, bool)

func (*SkipList) Remove

func (skipList *SkipList) Remove(score int)

* 删除对应分数的所有数据