<p>OK, so I'm learning go. Typing in the sample code through the book and doing the exercises at the end of the chapters. The last chapter covered standard library and in particular the container/list package. The exercise : Using the Go documentation and a package from the standard library build a doubly linked list, fill it with a few values, print it, then remove all values and print again. </p>
<p>All that to ask this question. Am I missing something? Why would you use a doubly linked list rather than a slice?</p>
<hr/>**评论：**<br/><br/>adonovan76: <pre><p>No, you're not missing anything. Traditional complexity analysis of algorithms using Big-O notation is based on the outdated assumption that all memory accesses have the same cost, but this is simply false for a modern computer. Locality is crucial. So, even though the number of instructions to insert an item into the middle of a list is O(n) for a slice and O(1) for a linked list, the slice runs faster because memcpy is extremely fast, and because the more important operation for a list is iterating over the elements, which is basically free for a slice but requires sequential pointer chasing, i.e. cache misses, for a linked list.</p>
<p>In short, slices and hash tables (maps) are all you need in almost all situations.</p></pre>ChristophBerger: <pre><p>Big-O is a means to reason about time complexity depending on the size of the input (denoted by <code>n</code>). The only question that Big-O answers is: How does an algorithm scale when the size of its input grows? Does it have constant time (O(1)), does it scale linearly (O(n)), by the square of the input size(O(n<sup>2)),</sup> etc? </p>
<p>As such, Big-O does not care if a particular O(n) algorithm on a particular CPU architecture is faster than another particular O(1) algorithm that does the same.</p>
<p>The point you make is very valid though: Big-O analysis is not sufficient for finding the fastest solution in a particular situation.</p></pre>DualRearWheels: <pre><p>Unless... Not related to Go but C, a year ago I had some work on high performance element iteration, and linked list outperformed array accessed by incrementing index (compiled on linux, gcc). I was surprised. Seems if every ns counts, just benchmark it.</p></pre>_ak: <pre><p>I'm surprised too. Did you find out why it was like this? Generally, data structures where elements are consecutive in memory are considered to be better for cache locality.</p></pre>DualRearWheels: <pre><p>No idea why. Maybe some compiler optimization. One is basically linked list containing next node and data pointer, other is pre allocated array of data pointers on heap. Linked lists just loops by loading pointer of next node, while array is in for loop where index number is incremented, then array[i] pointer loaded.</p>
<p>I expected array to beat linked list, but opposite happened. Maybe loading of next pointer is faster than array index lookup? (increment of i + memory lookup of array[0] + sizeof(array)*i under the hood?) Just guessing.</p>
<p>Now to think of it, I don't remember results of p++ test and if run faster (probably not, as we kept linked list implementation). Basically instead of (pseudo code):</p>
<pre><code>for (i=0; i <n; i++)
p = array[i]
</code></pre>
<p>we could do:</p>
<pre><code>for (p=array[0]; ; p++)
....
</code></pre>
<p>I guess this uses only one increment operation on pointer and is faster than using index i, but this comes down to assembly analysis.</p></pre>Redundancy_: <pre><p>Perhaps the point is not that a doubly linked list is the right answer to many problems, it's that it's a foundation to building many other data structures that is easily explained and understood and implemented.</p>
<p>A Trie or Red Black tree might be more practical, but they take a lot more work, even if they're based on similar core skills and understanding from the point of view of the language.</p></pre>PsyWolf: <pre><p>Slices are implemented using arrays which means they have similar performance characteristics. This really isn't a go specific question since nearly every langue has both array lists and linked lists. Here's a good summary of when you may want to use one over another. <a href="http://stackoverflow.com/questions/393556/when-to-use-a-linked-list-over-an-array-array-list" rel="nofollow">http://stackoverflow.com/questions/393556/when-to-use-a-linked-list-over-an-array-array-list</a></p></pre>ops_man: <pre><p>I'm specifically asking about slices which I believe while similar to type in other languages are golang central. According to the link you provided I incurred - although with limited experience - that slices (underlying array) would seem to be always preferable to linked list. </p>
<p>The standard library and others have implemented Most if not all of the functionality of linked list with a slice data type. Unless linked list in go are implemented (extended by the standard library) differently. </p>
<p>I'm new so I don't understand all the lingo. Maybe I'm just asking the question the wrong way. But I don't see how in go a linked list as used traditionally(?) would be preferable to a slice. </p></pre>izuriel: <pre><p>You have to look at the cost of each operation. Not just in big-O terms either but resources as well. When you append to a slice is new memory being allocated? How many appends are fixing to happen? How large is each value stored? Compare that to resources spent with a linked list. Another thing to consider is that the doubly linked list is quick to insert and remove from both the front and rear. So when inserts and removals are high that's a good time to use the linked list, especially since neither operation requires the entire data structure. Of you need random access, however some kind of array backed structure will be more efficient. </p>
<p>Slices in their Go form are pretty unique to Go, but the function like an ArrayList which every other language features in some form (essentially a dynamically sized array). So don't get hung up on the implementation and think more behavior to find counterparts. </p></pre>garoththorp: <pre><p>Linked lists are very rarely practical in the real world. Consider: for storing ints, you need two ints worth of data for each node, minimum. And then you can't even directly access elements without iterating.</p>
<p>Yeah, use slices homie.</p></pre>joncalhoun: <pre><p>There are unique benefits of a double linked list that make them beneficial over something like a slice. For example, you can remove something from a doubly linked list in constant time, but removing an item from the middle of a slice likely isn't constant time. Instead I <em>THINK</em> the best way to do this is to do something like:</p>
<pre><code>slice = append(slice[:i], slice[i+1:]...)
</code></pre>
<p>Assuming I didn't miss something, this is not constant time as it varies based on the size of the remaining slice after the index of whatever you are deleting.</p>
<p>One example of where a linked list can be useful over a slice is when implementing a least recently used cache. </p>
<p>For an example of this, Java has a <a href="http://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html" rel="nofollow">LinkedHashMap</a> class that is both a map and a linked list. By using both a linked list and a map this class is able to achieve constant time lookup for items in when searching for them in the cache (using the map), and if an item needs to be removed from the cache because it is full you can find the least recently used item in constant time as well. IIRC you can also update an item to be the most recently used item in the cache in constant time as well with this class, but it has been a while. </p>
<p>While the <code>LinkedHashMap</code> is a Java class, it wouldn't be far fetched to use a linked list and a map to create something similar in Go, albeit without the generics, and in that case you would likely be better off using a doubly linked list.</p>
<p>Editing just to say that I meant they are sometimes better than slices depending on the unique case, but not always. Hope that was clear.</p></pre>velco: <pre><p>By default use slices, period.</p>
<p>If you have performance problems, it is possible, depending on the concrete program and program input, a linked list to perform better.</p>
<p>It's just another, rarely used, tool.</p></pre>20CharsOrLess: <pre><p>There are a variety of applications for a doubly linked list. For example if you are building an LRU cache the standard implementation is to use a data structure constructed on a Hashtable and a Doubly Linked List. <a href="https://www.quora.com/What-is-the-best-way-to-Implement-a-LRU-Cache" rel="nofollow">https://www.quora.com/What-is-the-best-way-to-Implement-a-LRU-Cache</a></p></pre>
