Last active
July 24, 2023 17:04
-
-
Save maxclav/9d047c1838320d56c6c9af2e8e6d1efe to your computer and use it in GitHub Desktop.
[WIP] Ordered Dictionary (LinkedHashMap) in Go (GoLang) without container/list pkg.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// orderedmap implements an ordered map (ordered dictionary or linked hash map). | |
// This can be useful in scenarios where we need to maintain the order of access and/or insertion (ex: LRU Cache). | |
// For learning purposes. Use container/list. | |
package orderedmap | |
func NewOrderedMap() *OrderedMap { | |
return &OrderedMap{ | |
dict: make(map[string]*Node), | |
} | |
} | |
type OrderedMap struct { | |
dict map[string]*Node | |
head *Node | |
tail *Node | |
} | |
func (od *OrderedMap) Set(key string, value any) { | |
if _, ok := od.dict[key]; ok { | |
// Key already exists, update the value if needed | |
// We can also change its position (order) if needed | |
// (Ex: LRU Cache where Set() is considered as "used") | |
// This could be easily done by removing it before adding it. | |
return | |
} | |
node := &Node{ | |
key: key, | |
value: value, | |
prev: od.tail, | |
} | |
if od.head == nil { | |
od.head = node | |
} | |
if od.tail != nil { | |
od.tail.next = node | |
} | |
od.tail = node | |
od.dict[key] = node | |
} | |
func (od *OrderedMap) Front(key string) (*Node, bool) { | |
if len(od.dict) == 0 { | |
return nil, false | |
} | |
return od.head, true | |
} | |
func (od *OrderedMap) Get(key string) (any, bool) { | |
if node, ok := od.dict[key]; ok { | |
return node.value, true | |
} | |
return nil, false | |
} | |
func (od *OrderedMap) Remove(key string) { | |
if node, ok := od.dict[key]; ok { | |
if node.prev != nil { | |
node.prev.next = node.next | |
} else { | |
od.head = node.next | |
} | |
if node.next != nil { | |
node.next.prev = node.prev | |
} else { | |
od.tail = node.prev | |
} | |
delete(od.dict, key) | |
} | |
} | |
func (od *OrderedMap) Keys() []string { | |
keys := make([]string, 0, len(od.dict)) | |
node := od.head | |
for node != nil { | |
keys = append(keys, node.key) | |
node = node.next | |
} | |
return keys | |
} | |
type Node struct { | |
key string | |
value any | |
prev *Node | |
next *Node | |
} |
Author
maxclav
commented
Jul 24, 2023
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment