Linked Lists

Linked lists are array-like lists that solve the issue of insertion and deletion of elements in an array. When you want to remove or add an element to an array you must move the rest of the elements in memory. This is costly to execution time which can easily be solved with linked lists.

Intro

In a linked list each entry is represented as a node that contains its own data and a pointer to the next item in the list. This allows nodes to be anywhere in memory and makes it easier to remove and insert new nodes into the list.

Since each node can be anywhere in memory when removing or adding an element the memory addresses of the existing elements do not need to change. The next sections cover the procedure of removing a node from a linked list and inserting a new node.

Removal

When removing nodes from a linked list you have to do three things. First, find the node that points to the node you want to remove. Then change the pointer in this node to point to the address that your removed node points to. Then delete the node you want gone, or if you are using a language with garbage collection allow it to be deleted by it having no reference to it in the program. And there you go you have deleted a node.

Insertion

When inserting a new node the process is similar to removal. First, decide where in the list you want the node to be. Then take the previous node and set its pointer to the address of your new node. The address that was in the previous node before must then be the address your new node points to. This part is important because without it the next node can be lost in memory or deleted.

Linked lists are similar to arrays. They allow for faster removal and insertion of data than an array. For a simple application, I would not recommend using a linked list.

Linked lists are useful when:

• you need time constant insertions and deletions
• you do not know the number of items that will be in a list
• there is no need for random access memory to the list elements
• you want to easily insert data into the middle of a list

Conversely, there are many cases where an array is preferable such as:

• when you need to randomly access list elements
• when the number of elements is known beforehand
• you need faster iteration through list elements
• when memory is constricted, due to the fact that arrays take up less memory than linked lists.

Linked lists are a good tool to have under your belt as a developer. They are a good substitution to an array in certain cases. So with that said, enjoy implementing this in your next project. . .