StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>In a linked list, each element has a pointer to the next element:</p> <pre><code>head -> item1 -> item2 -> item3 -> etc. </code></pre> <p>To access <code>item3</code>, you can see clearly that you need to walk from the head through every node until you reach item3, since you cannot jump directly.</p> <p>Thus, if I wanted to print the value of each element, if I write this:</p> <pre><code>for(int i = 0; i < 4; i++) { System.out.println(list.get(i)); } </code></pre> <p>what happens is this:</p> <pre><code>head -> print head head -> item1 -> print item1 head -> item1 -> item2 -> print item2 head -> item1 -> item2 -> item3 print item3 </code></pre> <p>This is <strong>horribly inefficient</strong> because every time you are indexing it restarts from the beginning of the list and goes through every item. This means that your complexity is effectively <code>O(N^2)</code> just to traverse the list!</p> <p>If instead I did this:</p> <pre><code>for(String s: list) { System.out.println(s); } </code></pre> <p>then what happens is this:</p> <pre><code>head -> print head -> item1 -> print item1 -> item2 -> print item2 etc. </code></pre> <p>all in a single traversal, which is <code>O(N)</code>.</p> <p>Now, going to the other implementation of <code>List</code> which is <code>ArrayList</code>, that one is backed by a simple array. In that case both of the above traversals are equivalent, since an array is contiguous so it allows random jumps to arbitrary positions.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload