Linked Lists

You may have worked with arrays before jumping on linked lists. Arrays are one of the most popular and simplest data structures. Both arrays and linked lists are linear data structures. But they have certain advantages and disadvantages over one another, that’s the reason why they exist.

This is how we represent an array, they store elements in a contagious fashion. If you haven’t heard of arrays then check out the following link. It covers everything you need to know about arrays.

All about Arrays

As you know, elements in an array are stored in contiguous memory locations. Here is a representation:

If we want to store say 5 elements in an array then we can do that

But what if we want to continuously update the number of elements in the array and the chunk of contiguous space available is less. Or even if the space is available we will have to copy elements from one location to another. That will cost us a lot of memory, So linked lists come to the rescue.

This doesn’t mean that arrays are of no use, there are certain advantages of arrays. Let’s look at the first then we will discuss linked lists and the disadvantages of arrays.
Arrays are stored contiguously that’s why each element are easily accessed. So if you have a case where you set the data once and you don’t have to update it. You just need to access it, then there is no better solution than storing them in an array.

But if you want to add some data to the existing one or delete some, then arrays are not efficient in this case. This is one of the major disadvantages of arrays.
For this reason, linked lists come into the picture.

One node of the linked list contains a data element and the address of the next node. Both data part and address part combined are known as a ‘node’.

Nodes can be at any place in the memory, the previous node will contain the address to the next node. Hence the insertion and deletion are easily done because we just need to update the address.

Based on the address of the nodes they contain there are 3 types of linked lists.

1. Singly Linked Lists
2. Doubly Linked Lists
3. Circular Linked Lists

原文链接：Linked Lists