Linkedlist Algorithm
On the other hand, since simple associated lists by themselves do not let random access to the data or any form of efficient indexing, many basic operations — such as obtaining the last node of the list, finding a node that contains a given datum, or locating the place where a new node should be inserted — may necessitate iterate through most or all of the list components. They can be used to implement several other common abstract data types, including lists, stacks, queues, associative arrays, and S-expressions, though it is not uncommon to implement those data structures directly without use a associated list as the basis. The problem of machine translation for natural language processing led Victor Yngve at Massachusetts Institute of technology (MIT) to use associated lists as data structures in his COMIT programming language for computer research in the field of linguistics. Several operating systems developed by Technical system adviser (originally of West Lafayette Indiana, and later of Chapel Hill, North Carolina) used singly associated lists as file structures. The now-classic diagram consisting of blocks representing list nodes with arrows indicating to successive list nodes looks in" program the logic theory machine" by Newell and Shaw in Proc.
package main
import "fmt"
/* v is the value of node; next is the pointer to next node */
type node struct {
v int
next *node
}
/* first node, called head. It points from first node to last node */
var head *node = nil
func (l *node) pushFront(val int) *node {
/* if there's no nodes, head points to l (first node) */
if head == nil {
l.v = val
l.next = nil
head = l
return l
} else {
/* create a new node equals to head */
nnode := new(node)
nnode = head
/* create a second node with new value and `next -> nnode`
* is this way, nnode2 is before nnode
*/
nnode2 := &node {
v: val,
next: nnode,
}
/* now head is equals nnode2 */
head = nnode2
return head
}
}
func (l *node) pushBack(val int) *node {
/* if there's no nodes, head points to l (first node) */
if head == nil {
l.v = val
l.next = nil
head = l
return l
} else {
/* read all list to last node */
for l.next != nil {
l = l.next
}
/* allocate a new portion of memory */
l.next = new(node)
l.next.v = val
l.next.next = nil
return l
}
}
func (l *node) popFront() *node {
if head == nil {
return head
}
/* create a new node equals to first node pointed by head */
cpnode := new(node)
cpnode = head.next
/* now head is equals cpnode (second node) */
head = cpnode
return head
}
func (l *node) popBack() *node {
if head == nil {
return head
}
/* create a new node equals to head */
cpnode := new(node)
cpnode = head
/* read list to the penultimate node */
for cpnode.next.next != nil {
cpnode = cpnode.next
}
/* the penultimate node points to null. In this way the last node is deleted */
cpnode.next = nil
return head
}
func main() {
lista := new(node)
lista.pushBack(25).pushBack(24).pushBack(32) /* lista: 25 24 32 */
lista.pushBack(56) /* lista: 25 24 32 56 */
lista.pushFront(36) /* lista: 36 25 24 32 56 */
lista.popFront() /* lista: 25 24 32 56 */
lista.popBack() /* lista: 25 24 32 */
/* read the list until head is not nil */
for head != nil {
fmt.Printf("%d ",head.v)
head = head.next /*head points to next node */
}
}
