A list is an abstract data type, where there are a number of items. In a list, the same item might occur more than once. These values are stored in sequential order, so we can refer to each item in the list by its position. Lists are very useful for a wide variety of operations and can be used to implement other data structures such as trees, queues or stacks, which will be intruoduced in later articles. Not all programming languages have lists built in however, so in the absence of a list, an array can be used. List's contents are shown in square brackets (the same as an array) and would look like this [42, 17, 19, 3, 18].
There are a number of functions that can be performed on a list data structure, and these functions are key when using a list to utilise other data strutures. These operations can be seen in the table below.
Using an Array
We can use an array to create a list, as an array can allow us to create an ordered set of values. One issue is that, as an array is a static data structure, it is only suitable for small lists and only if the amount is known in advance. The length of an array cannot be changed.
Arrays have other disadvantages too, such as the time taken to add an item to the start of an array. When doing this, each value in the array has to be moved into the adjacent spot, to make space at the start of the array, as seen in this animation:
The same happens when deleting an item from a list created with an array. When an item is removed the space does not remain, all of the items will move towards the front of the list until the space is filled.
Linked Lists
Now that we know how to implement an array using a list, imagine a world where the list elements are stored wherever there is space, and are linked to form a sequence. A world where the drawbacks that arrays have (fixed size, small size, set order) do not exist. That world is the world of linked lists.
A linked list is a collection of nodes (items) that form a linear ordering. This ordering is determined in a similar manner to the game 'follow the leader', with each node containing a pointer to the next node and so on.
Like an array, these lists maintain an order, with those elements staying in that order. This order is determined by the chain of links (the pointers) which determine the next node that the list links to. A linked list, unlike an array, doesn't have a fixed size, and can grow to store all of the information from the list. Linked lists do not record any index numbers, so when looking at nodes, there is no way to tell the position that the item holds in the list.
When adding a node to the beginning of a linked list, it is considerably faster than adding a value to the beginning of a list using an array. As seen in this video:
Similarly, the deletion process for a linked list is much simpler, following these three steps:
Find the node before the one that you want to delete
Change the next pointer to point to the node after the one that you are deleting
Delete the node
It's that simple!