arazmj /
gerdu
| Total Lines | 58 |
| Duplicated Lines | 0 % |
| Changes | 0 | ||
| 1 | // Package dlinklist implements a doubly linked list as backing data structure for cache operations |
||
| 2 | package dlinklist |
||
| 3 | |||
| 4 | // Node data structure |
||
| 5 | type Node struct { |
||
| 6 | next *Node |
||
| 7 | prev *Node |
||
| 8 | Key string |
||
| 9 | Value string |
||
| 10 | Freq int |
||
| 11 | } |
||
| 12 | |||
| 13 | // DLinkedList data structure |
||
| 14 | type DLinkedList struct { |
||
| 15 | head *Node |
||
| 16 | tail *Node |
||
| 17 | size int |
||
| 18 | } |
||
| 19 | |||
| 20 | // NewLinkedList constructor |
||
| 21 | func NewLinkedList() *DLinkedList { |
||
| 22 | head := &Node{} |
||
| 23 | tail := &Node{} |
||
| 24 | head.next = tail |
||
| 25 | tail.prev = head |
||
| 26 | return &DLinkedList{ |
||
| 27 | head: head, |
||
| 28 | tail: tail, |
||
| 29 | } |
||
| 30 | } |
||
| 31 | |||
| 32 | // AddNode adds a new node to the tail of of linked list |
||
| 33 | func (c *DLinkedList) AddNode(node *Node) { |
||
| 34 | next := c.head.next |
||
| 35 | c.head.next = node |
||
| 36 | next.prev = node |
||
| 37 | node.next = next |
||
| 38 | node.prev = c.head |
||
| 39 | c.size++ |
||
| 40 | } |
||
| 41 | |||
| 42 | // RemoveNode removes a node |
||
| 43 | func (c *DLinkedList) RemoveNode(node *Node) { |
||
| 44 | prev := node.prev |
||
| 45 | next := node.next |
||
| 46 | prev.next = next |
||
| 47 | next.prev = prev |
||
| 48 | c.size-- |
||
| 49 | } |
||
| 50 | |||
| 51 | // PopTail pops a node from the beginning of the linked list |
||
| 52 | func (c *DLinkedList) PopTail() *Node { |
||
| 53 | prev := c.tail.prev |
||
| 54 | c.RemoveNode(prev) |
||
| 55 | return prev |
||
| 56 | } |
||
| 57 | |||
| 58 | func (c *DLinkedList) Size() int { |
||
|
introduced
by
|
|||
| 59 | return c.size |
||
| 60 | } |
||
| 61 |
Loading history...