Linked List vs Array

The advantage of a linked list data structure over a plain array is that you can easily insert new items to the linked list.

There is a good example and analogy in this post:

"You have some errands to do, so you grab a piece of paper and write:

• bank
• groceries
• drop off drycleaning

Then you remember that you also need to buy stamps. Because of the geography of your town, you need to do that after the bank. You could copy your whole list onto a new piece of paper:

• bank
• stamps
• groceries
• drop off drycleaning

or you could scribble on the one you had:

• bank ....... STAMPS
• groceries
• drop off drycleaning

As you thought of other errands, you might write them at the bottom of the list, but with arrows reminding yourself what order to do them in. This is a linked list. It's quicker and easier than copying the whole list around every time you add something.

Then your cell phone rings while you're at the bank "hey, I got the stamps, don't pick up any more". You just cross STAMPS off the list, you don't rewrite a whole new one without STAMPS in it.

Now you could actually implement an errands list in code (maybe an app that puts your errands in order based on your geography) and there's a reasonable chance you would actually use a linked list for that in code. You want to add and remove lots of items, order matters, but you don't want to recopy the whole list after each insertion or deletion."

Sources:

• What are concrete examples of use cases of linked lists?

Keywords:
Programming, Data Structures, Algorithms and Data Structures