Linked Lists

Data structures Series  – Blog 02


Linked Lists

Welcome back! Let’s continue with the data structures theme. Here’s the blog on the next data structure – that would solve the problem we had with arrays. Essentially, these two problems :

a. Arrays had fixed size , that needed to be specified when we define them. Resizing is an issue. So, developer might allocate a worst case array size, that may not be efficient if the number of elements to be held varies.

b. When we want to rearrange data in an array or insert data in between or front of an array, it  gets expensive.

Linked lists are the data structures which will help us in addressing these issues. Arrays and linked lists both essentially provide a way to store data for a client. Although linked lists to be discussed today, are good for cases arrays may not be great, they do come with their own limitations. We will cover it all in this blog, keep on reading.


Basic Stuff

If you have ever wondered why people often quiz you about linked lists? Wonder no more. It’s  because these are the most basic data structures that form the foundation for understanding more advanced data structures ( such as: binary trees, queues) etc.

Let’s suppose you need to write some basic C program to read all words (strings) contained in an input file. The first question that we would have is – How would you store the words read by the program? If we used a string array here, what would be the size to be allocated for the array? The number of words in the file is not known.

In this case, if we used a linked list, we can read words without wasting memory or be running out of memory (as would be the case, if we used arrays). This is because, as the name implies, linked lists are nothing but a list of elements linked together using a pointer parameter, in addition to the data that needs to be held – words in this case. So, the items to be inserted are just linked to the list, dynamically as and when required.

Now that we have a use case in mind, let’s learn about the internals of linked lists, operations supported and some overheads associated with their usage.


Internals

Linked list data structure are similar to arrays, but use an extra parameter – a pointer to link the items together. With this additional overhead of pointer per entry of data to be held, we can overcome the disadvantages of arrays and use memory efficiently. Linked lists use a different strategy for allocating memory for elements as compared to arrays. They allocate memory per element, when a new element needs to be inserted, not as a block as in case of arrays.

As shown below, a set of integer elements are organized in a linked list as shown on the right. We can note that there is an extra address field, that links the items together in the list. Values {2,3,5,7,8} are the data elements. We can clear;y see there is an overhead per element, to hold the pointer to next data element, in case of linked lists. But, even with this, we may be more memory efficient than arrays, when we perform operations such as always insert to the top of the list or storing elements in memory when the number of elements is not known apriori.

arr_ll
Fig 1. Arrays and linked lists elements in memory

We define a linked list element/node and a create a linked list, as below :

/* define node element for a Singly linked list*/
typedef struct Node{
int data;
Node* next;
}Node;

/* function to create and return linked list node */
Node* create_node(int data){
Node* n = (Node*) malloc(sizeof(Node));
n->data = data; // store the data
n->next = NULL; // initialize next address to NULL
return n;
}

/* Example code to create a linked list of nodes 
*  Creates a linked list with three data elements/nodes 
*  Linked list : n1->n2->n3->NULL */ 

Node* create_test_list(){

Node* n1 = create_node(10);
Node* n2 = create_node(20);
Node* n3 = create_node(30);

// update pointers
n1->next = n2; // n1 holds pointer to n2
n2->next = n3; //n2  holds pointer to n3

// n3 is the last node of this list and 
// next shall be stored as NULL to imply this.

}

Operations supported

We can implement various operations on linked lists such as insert(), delete(), lookup(), hasloop(), removeloop()  and so on. It would be a good idea to write code for these operations, to understand linked lists better. Check [1] and [2] under references below to get started.


Doubly Linked List

These are similar to singly linked lists discussed above. But, instead of holding pointer only to the next element, there is an additional pointer per node to point to the previous element as well. Why do we need them? Wait for next week’s blog 🙂 ll1.png

/* Singly Linked list node */
typedef struct Node{
int data;
Node* next;
} Node;

/* Doubly Linked list node */
typedef struct d_Node{
int data;
Node* next ; 
Node* previous; // extra pointer in doubly linked list
} d_Node;


Drawbacks

What do you think would be the drawback of a linked list, other than the storage of extra parameter – i.e., a pointer per element. Yes! It is the insert at the nth location and also lookup nth element operations. In arrays, we had an O(1) look up and also O(1) updates.

But, with linked lists, we have to iterate all the n-1 nodes, to find the place to insert nth node to the list. Also, if we want to look-up nth node, we need to traverse n-1 nodes, before we get the value of nth node- resulting in O(n) cost.

Visual is always better to understand. Please check the picture below.

ll1
Fig 2. Insert at nth position, operation on arrays and linked list

 


Further Reading

  1. Linked list problems (Stanford)
  2. Solve some problems related to linked lists

Next, we shall explore the Binary Search Tree data structure which is realized using a doubly linked list discussed here. As always, write to me at decodergirlblog@gmail.com if you have any queries or suggestions. I would love to hear from you. Until then, keep decoding and enjoying your coffee ! 😉

 

Did you know?

More coffee you donate, higher is your coder karma! Oh! there shall also be more blogs published here. Thank you for being awesome! 😀

$1.00

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s