LinkedLists vs. Arrays

At some point during the past few lectures you may have asked yourself, “Hmm… why the would anyone ever want to use a LinkedList? Aren’t array’s good enough?”

There is one major advantage of using a LinkedList over an array: flexibility in size. As you should recall, when declaring an array, the size of the array must be set upon creation. If you declare you array to be of size 3, you’ll never be able to stick a 4th element into it. If you run out of space in your array, your only option is to create a brand new, larger array and copy the old data from the old array into the new one.

In comparison, LinkedLists are flexible in size. This is because as you add things to the LinkedList, you must simply create a new Node and connect it to your existing list. Think of it like having a tower of legos and adding an extra piece on the top (or bottom, or middle… wherever you like really).

Tldr: LinkedLists are expandable in size where as arrays are not.

Besides this difference, another major difference between arrays and LinkedLists is the way the data is stored in memory. Imagine memory space being represented as an empty room. Items stored in an array would adjacent in memory, like people standing shoulder to shoulder in a line (I’d put a picture here, but the stock photos are pretty terrible, so use your imagination!). If you stood facing the first person in the line of people and took one step down the line, you’d face the second person. If you took another step down the line you’d be facing the third person and so on. The correlation between you taking a step and facing the next person is kind of like indexing in an array.

Items in a LinkedList are stored much differently in memory. Using the same analogy, Nodes in a LinkedList would be like multiple people spread out about the room. Even though these people aren’t directly next to each other, they know where there neighbor is. If you stand facing the first person/node in this list and want to go to see the next person/node, all you have to do is ask first where his neighbor is and go where he points.

Tldr, items in arrays are adjacent in memory & items in LinkedLists are spread out (but still connected).

Leave a Reply

Your email address will not be published. Required fields are marked *