How to link LinkedList nodes to map values

user_1395740 0
Viewed 478

I want to implement a graph data structure, where each node is represented by:

type Node struct {
    root  string
    links []*Node
}

Basically each node has a value root and a list of links, for each link a only want to store a pointer to it, since the memory of the struct will be allocated and owned by a map:

rooturl := "root"
graph := Node{rooturl, []*Node{}}
graphMap := make(map[string]Node)
graphMap[rooturl] = graph

The problem comes when I try to append a pointer to a newly created Node:

u := "new node"
// if the link is not stored in the graph not create a new node
if _, exists := graphMap[u]; !exists {
    graphMap[u] = Node{u, []*Node{}}
}
// add the links to the graph
graphMap[rooturl].links = append(graphMap[rooturl].links, &graphMap[u])

I get two errors:

cannot assign to struct field graphMap[rooturl].links in map

and

cannot take the address of graphMap[u]

How should I solve this properly? I would also like the need to query the map twice with graphMap[rooturl].links when appending (but since I cannot take a pointer or a reference to it I don't know how)

go pointers linked-list dictionary
2 Answers

Things you trying to achieve are not possible the way you do it. It's about addressability and assignability. You should search language specification for this keywoards. Map values aren't addressable, so struct field in that value is not assignable. Also your data structure design looks not very efficient at least for me.

Seems to me there are no reasons to store values in a map, references would be good enough

type Node struct {
    root  string
    links []*Node
}
//////
rooturl := "root"
graph := Node{rooturl, []*Node{}}
graphMap := make(map[string]*Node)
graphMap[rooturl] = &graph
u := "new node"
// if the link is not stored in the graph not create a new node
if _, exists := graphMap[u]; !exists {
    graphMap[u] = &Node{u, []*Node{}}
}
// add the links to the graph
graphMap[rooturl].links = append(graphMap[rooturl].links, graphMap[u])

Working example

If you prefer to keep actual values in a map anyway, you need not tree structure at all. It looks like unneeded overhead. Information stored in a map would be enough for any operations.

type Node string
type Graph map[Node][]Node
////
rooturl := Node("root")
graph := make(Graph)
graph[rooturl] = make([]Node, 0)
u := Node("new node")
// if the link is not stored in the graph not create a new node
if node, exists := graph[u]; !exists {
    graph[u] = make([]Node, 0)
    graph[rooturl] = append(graph[rooturl], u)
}

Working example

user_43741090

Since go is a garbage collected language, you don't really need a notion of the map "owning" the node's memory. You can probably just store pointers in the map.

https://play.golang.org/p/DpcsIqg0Trx

user_14795160
Related