What slice vs. container/list (Bjarne Stroustrup: Why you should avoid Linked Lists)

[Gyu-Ho Lee]

http://www.youtube.com/watch?v=YQs6IC-vgmo
Bjarne Stroustrup: Why you should avoid Linked Lists

I happen to see this clip where he explains why vector is better than linked list.

How about in Go? I was coding some graph algorithms that do a lot of insertion and deletion in a list of nodes. First I implemented it with slice, but later switched it to container/list because I wanted the following method:

// Delete a Vertex from the graph.

func (G *Graph) DeleteVertex(A *Vertex) {

for vtx := G.VertexList.Front(); vtx != nil; vtx = vtx.Next() {

if vtx.Value.(*Vertex) == A {

// remove from the graph

G.VertexList.Remove(vtx)

}

}

// traverse all the outgoing edge(vertex)

// remove this vertex A from the predecessor of the vertices,

// also delete the edges from A

for edge := A.GetEdgeListFromThisVertex().Front(); edge != nil; edge = edge.Next() {

G.DeleteEdgeFrom(A, edge.Value.(*Edge).DestinationVertex)

for vtx := edge.Value.(*Edge).DestinationVertex.Predecessor.Front(); vtx != nil; vtx = vtx.Next() {

edge.Value.(*Edge).DestinationVertex.Predecessor.Remove(vtx)

}

}

}

But I've just found out SliceTricks (https://code.google.com/p/go-wiki/wiki/SliceTricks) that does anything I want.

Then why and when should I use container/list? Now I get used to it, but sometimes dealing with type interface {} feels tedious.

[Gyu-Ho Lee]

What slice vs. container/list -> Which data structure should I use? slice vs. container/list ...

Sorry for typo.

[Dave Cheney]

Always use a slice. 

Dave

On 27 Jan 2014, at 15:53, Gyu-Ho Lee <gyuh...@gmail.com> wrote:

What slice vs. container/list -> Which data structure should I use? slice vs. container/list ...

Sorry for typo.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Erwin]

It depends a lot on the number of elements in your lists, whether a true list or a slice will be more efficient when you need to do many deletions in the 'middle' of the list. The more elements, the less attractive a slice becomes. When the ordering of the elements isn't important, it is most efficient to use a slice and deleting an element by replacing it by the last element in the slice and reslicing the slice to shrink the len by 1 (as explained in the SliceTricks wiki.  

[Dmitry Vyukov]

There are ways to mitigate the deletion problem -- e.g. the swap trick
you mentioned or just marking the elements as logically deleted. But
it's impossible to mitigate the problem of slowness of walking linked
lists.

[Gyu-Ho Lee]

Thanks a lot!

[manohar12...@gmail.com]

I switched from slice to list.List

list.List -> slice -> list.List -> slice

Somehow the performance din't decrease much, it was only about 7ms

While doing graphs, with Golang,

 the list.List or slice is not important,

 it is the algorithm choice of how list or slice is used

 gives the TLE (Time Limit Exceeded) or pass the test

Best of luck