Algorithm - 无序链表

说明

符号表中使用的数据结构的一个简单选择是链表，每个结点存储一个键值对，如算法 3.1 中 的代码所示。get() 的实现即为遍历链表，用 equals() 方法比较需被查找的键和每个结点中的键。如果匹配成功我们就返回相应的值，否则我们返回 null。put() 的实现也是遍历链表， 用 equals() 方法比较需被查找的键和每个结点中的键。如果匹配成功我们就用第二个参数指定 的值更新和该键相关联的值，否则我们就用给定的键值对创建一个新的结点并将其插入到链表的 开头。这种方法也被称为顺序查找:在查找中我们一个一个地顺序遍历符号表中的所有键并使用 equals() 方法来寻找与被查找的键匹配的键。

Code

package main

import (
	"fmt"
)

// node - 节点结构
type node struct {
	value string
	key   string
}

// list - 链表
type list struct {
	current *node
	next    *list
}

//	String - 链表输出
func (li *list) String() string {
	return fmt.Sprintf("%s -> %s", li.current, li.next)
}

// String - 节点输出
func (nd *node) String() string {
	return fmt.Sprintf("%s", nd.value)
}

func main() {
	newList := &list{}

	newList.put("a", "valA")
	newList.put("b", "valB")
	newList.put("c", "valC")

	newList.delete("c")
	newList.delete("b")
	val, exist := newList.get("a")

	fmt.Printf("%s exist: %v list: %s \n", val, exist, newList)
}

// 修改/添加 key value
func (li *list) put(key, val string) {
	if li.isEmpty() {
		// 空链表是直接加到第一个元素
		li.current = &node{value: val, key: key}
		li.next = &list{}
		return
	}
	// 不为空时,查找是否有节点和key匹配
	nd := checkKey(li, key)
	if nd == nil {
		// 没有节点匹配,需要添加到链表头部
		li.current, li.next = &node{value: val, key: key}, &list{current: li.current, next: li.next}
	} else {
		// 匹配到则修改value
		nd.current.value = val
	}
}

// 获取key对应的value
func (li *list) get(key string) (val string, exist bool) {
	if li.isEmpty() {
		// 空链表返回 false
		return "", false
	}
	// 匹配查找
	nd := checkKey(li, key)
	if nd != nil {
		// 找到返回value 和 true
		return nd.current.value, true
	}
	// 其他情况返回false
	return "", false
}

// 删除key对应的节点
func (li *list) delete(key string) {
	if li.isEmpty() {
		// 空链表直接返回
		return
	}
	// 查找匹配节点
	nd := checkKey(li, key)
	if nd != nil {
		// 找到节点
		if nd.next != nil {
			// 有后续链表时,把后面的前移
			nd.current = nd.next.current
			nd.next = nd.next.next
		} else {
			// 如果是最后一个节点,把当前节点为nil
			nd.current = nil
			nd.next = nil
		}
	}
}

// 查找匹配key对应的节点
func checkKey(ls *list, key string) (lt *list) {
	if ls.current != nil && ls.current.key == key {
		// 匹配key
		return ls
	}
	if ls.next == nil {
		// 无后续链表则直接结束nil-代表没找到
		return nil
	}
	// 递归查找后续的链表
	return checkKey(ls.next, key)
}

// 判断是否为空链表
func (li *list) isEmpty() bool {
	return list{} == *li
}