go实现双向链表并使用iterater遍历
package main
import (
"strings"
"strconv"
"fmt"
)
/**
双向链表
*/
type DoubleLinkedList struct {
//链表头节点
head *Node
//链表尾部节点
tail *Node
//长度
size int
}
/**
遍历器接口
*/
type Interater interface{
/**
是否还有下一个
*/
hasNext() bool
/**
下一个节点
*/
next() *Node
}
/**
遍历器
*/
type ListInterater struct {
list *DoubleLinkedList
currentNode *Node
}
/**
遍历器是否还有下一个节点
*/
func (inter *ListInterater) hasNext() bool{
if inter.currentNode==nil && inter.list.head!=nil {
return true
}else if inter.currentNode==nil && inter.list.head==nil {
return false
}else{
return inter.currentNode.next!=nil
}
}
/**
遍历器获取下一个节点
*/
func (inter *ListInterater) next() *Node{
if inter.currentNode==nil && inter.list.head!=nil{
inter.currentNode = inter.list.head
}else if(inter.currentNode==nil && inter.list.head==nil){
return nil
}else{
inter.currentNode = inter.currentNode.next
}
return inter.currentNode
}
/**
节点
*/
type Node struct {
data interface{}
prev *Node
next *Node
}
func (list *DoubleLinkedList) GetHead() *Node {
return list.head
}
func (list *DoubleLinkedList) GetTail() *Node {
return list.tail
}
func (list *DoubleLinkedList) Size() int {
return list.size
}
func (list *DoubleLinkedList) initFromNode(node *Node) {
list.head = node
list.tail = node
list.size = 1
}
func (list *DoubleLinkedList) addHead(node *Node){
oldHead :=list.head
oldHead.prev = node
node.next = oldHead
node.prev = nil
list.head = node
list.size++
}
/**
获取链表的遍历器
*/
func (list *DoubleLinkedList) Iterater() *ListInterater{
inter:=ListInterater{
list:list,
currentNode:nil,
}
return &inter
}
/**
从头部添加节点
*/
func (list *DoubleLinkedList) AddFromHead(node *Node) {
if list.head==nil && list.tail==nil {
list.initFromNode(node)
}else{
list.addHead(node)
}
}
/**
从尾部添加节点
*/
func (list *DoubleLinkedList) addTail(node *Node){
oldTail :=list.tail
oldTail.next = node
node.prev = oldTail
node.next = nil
list.tail = node
list.size++
}
/**
删除指定位置节点
*/
func (list *DoubleLinkedList) Remove(index int) {
node:=list.Get(index)
if node==nil {
return
}
prev:=node.prev
next:=node.next
if prev!=nil {
prev.next=next
}
if next!=nil {
next.prev=prev
}
list.size--
}
/**
从后面追加节点
*/
func (list *DoubleLinkedList) Append(node *Node) {
if list.head==nil && list.tail==nil {
list.initFromNode(node)
}else{
list.addTail(node)
}
}
/**
获取指定位置节点
*/
func (list *DoubleLinkedList) Get(index int) *Node {
next:=list.head
for i:=0;i
本文名称:go实现双向链表并使用iterater遍历
当前URL:http://scyanting.com/article/jchpho.html