アルゴリズム4:単一チェーンテーブルに関する操作


以下の操作を実現


1.空のシングルチェーンテーブルであるか否かを判断する.単一チェーンテーブルの長さ3.ヘッダノード4を取得する.ヘッダから要素5を追加する.末尾から要素6を追加する.指定の場所に要素7を追加する.指定要素8を削除する.指定位置の要素9を削除する.要素10が含むか否かを判断する.シングルチェーンテーブルの反転

linkedListパッケージコードは以下の通りです。

package linkedList

import "fmt"

type Object interface{}

type Node struct {
	Data Object
	Next *Node
}

type List struct {
	headNode *Node //   
}

//          
func (this *List) IsEmpty() bool {
	if this.headNode == nil {
		return true
	} else {
		return false
	}
}

//      
func (this *List) Length() int {
	cur := this.headNode
	count := 0
	for cur != nil {
		count++
		cur = cur.Next
	}
	return count
}

//      
func (this *List) GetHeadNode() *Node {
	return this.headNode
}

//       
func (this *List) Add(data Object) {
	node := &Node{Data: data}
	node.Next = this.headNode
	this.headNode = node
}

//       
func (this *List) Append(data Object) {
	node := &Node{Data: data}
	if this.IsEmpty() {
		this.headNode = node
	} else {
		cur := this.headNode
		for cur.Next != nil {
			cur = cur.Next
		}
		cur.Next = node
	}
}

//         
func (this *List) Insert(index int, data Object) {
	if index <= 0 {
		this.Add(data)
	} else if index >= this.Length() {
		this.Append(data)
	} else {
		// fmt.Println("hello")
		pre := this.headNode
		count := 0
		for count < (index - 1) {
			pre = pre.Next
			count++

		}
		//      ,pre  index -1   
		node := &Node{Data: data}
		node.Next = pre.Next
		pre.Next = node
	}
}

//      
func (this *List) Remove(data Object) {
	pre := this.headNode

	if pre.Data == data {
		this.headNode = pre.Next
	} else {
		for pre.Next != nil {
			if pre.Next.Data == data {
				pre.Next = pre.Next.Next
			} else {
				pre = pre.Next
			}
		}
	}
}

//         
func (this *List) RemoveAtIndex(index int) {
	pre := this.headNode
	if index <= 0 {
		this.headNode = pre.Next
	} else if index >= this.Length() {
		fmt.Println("index out of range") //   err
	} else {
		count := 0 //index = 3
		for count != (index-1) && pre.Next != nil {
			count++        //2
			pre = pre.Next //2
		}
		pre.Next = pre.Next.Next
	}
}

//        
func (this *List) Contain(data Object) bool {
	cur := this.headNode
	for cur != nil {
		if cur.Data == data {
			return true
		}
		cur = cur.Next
	}
	return false
}

//    ,         
func (this *List) ReverseList() List {
	pre := this.headNode
	list := List{}
	for pre != nil {
		list.Add(pre.Data)
		pre = pre.Next
	}
	return list
}

テストコードはmainです。go中は以下の通り

package main

import (
	"fmt"
	"test/linkedList/linkedList"
)

func main() {
	list := linkedList.List{}

	//1.          2, 3, 4, 5
	list.Append(1)
	list.Append(2)
	list.Append(3)
	list.Append(4)

	//2.       head_node
	list.Add("head_node")
	fmt.Println("  ======", list.Length())

	//3.        
	bool := list.IsEmpty()
	fmt.Println(bool)

	//4.     2     2indexValue
	list.Insert(2, "2_index_value")
	travselLinkList(&list)

	//5.      2_index_value
	isContain := list.Contain("2_index_value")
	fmt.Println("isContain[2_index_value]:", isContain)

	//6.    2_index_value
	list.Remove("2_index_value")
	travselLinkList(&list)

	//7.   2    
	list.RemoveAtIndex(2)

	//8.     
	listReverse := list.ReverseList()

	fmt.Println("  ======", list.Length())
	travselLinkList(&list)
	travselLinkList(&listReverse)

}

func travselLinkList(list *linkedList.List) {
	//  
	head := list.GetHeadNode()
	for head != nil {
		fmt.Println(head.Data)
		head = head.Next
	}
	fmt.Println("--------------------")
}