Linked List

For the first meeting, I've learned about LINKED LIST. So what is linked list? Linked list is a dynamic data structure, where each element is a separate object. If in array we can easily access the elements in it by the index--because it stores the value in a consecutive memory location, in linked list we can’t do that because in linked list it uses random memory location. Now if you think “Then, isn't array better than?” well in array you can’t easily do insertions and deletions, but in linked list you can easily do push(for insertion) or pop(for deletion). Other than that, if in array you have to give a fixed memory to use in your program, in linked list the number of nodes is not fixed and can grow or shrink on demand, hence it’s called a dynamic data structure. This feature is very useful when you have to deal with an unknown number of objects. One of the disadvantage of linked list is that it uses more memory compares with an array, it adds an extra 4 bytes (on 32-bit CPU) to store a reference to the next node.       

            I have mentioned nodes before, so, what is it? In linked list we usually call each element in it as a node. A node has two things in it, a value, and a reference to the next node. The last node has a reference to NULL. The first node of a linked list is usually called the head of the list and the last node is called the tail of the list. If the list is empty then the head is a NULL reference.

            There are several types of linked list, the first one is a single linked list which was described above and the second one is a double linked list. A double linked list has the same meaning as a single linked list, just that it has an addition of a reference to the previous node too. There is also a circular linked list which has no head or tail because the tail is connected to the head. Another one is multilinked list, it has multiple additional lists from a certain mode.

Single Linked List

Double Linked List

Circular Linked List

So now I’m going to give an example on how to do the operations.

1.      Insert nodes.

To insert a new node we can do pushHead or pushTail or pushMid.

Firstly, we will need to create a structure that defines a node. This will need to include at least one variable for data and one pointer to refer to the next node.

•  pushHead

When adding a node to the start of the list we need to take care of the following things:

a.   If the node to be added is the first node in the list then the Tail node and Head node will be the same. 

b.   If a node to be added to the list is not the first node then we need to store the head node in a temporary variable and set the Head node to the newly added node and update its next pointer to the temporary node (that was the Head node initially). In this way our newly added node becomes the Head node and it starts pointing to the older Head node that has become the second node in the list.

• pushTail

This method is used to add the node at the end of the list. It is similar to the pushHead method except we update the Tail node here instead of Head Node. 

1. If there is no node in the list then the Head node and Tail node will be the same. 
2. If we have one or more nodes then we will store the Tail node in some temporary variable and set the Tail node to the newly added node and we will update the next pointer of our temporary node to the Tail node.

• pushMid

This method is used to add the node in the middle of the list. It is just a combination of pushHead and pushTail with an addition of another function.

 2.  Remove nodes.

To remove a node we con do popHead or popTail or popMid.

• popHead 

For removing the first element in the list we must have the following points in mind:

a.   List count should not be zero. 

b.   If there is only one element in the list then the Head and Tail node must be set to null or we can also call the Clear method since there is no element in the list. 

c.   If there is more than one node in the list then we need to set the Head node to the next pointer of the Head node (that is the second node). By doing that the second element in the list becomes the Head node.

• popTail

For removing the last element in the list we must check the following:

a.   List count should not be zero. 

b.   If there is only one element in the list then the Head and Tail nodes must be set to null or we can also call the Clear method since there is no element in the list. 

c.   If there is more than one node in the list then we need to iterate among all the nodes and need to retain the previous node (because this node is going to become the Tail node). While iterating among all the nodes we need to find the node whose next pointer is null because that node is the Tail node. Since we are also maintaining the previous node we will also change its next pointer to null and set the Tail node to the previous node.

 3. View all.

To view all nodes that we have input we can make a function.

That’s all for today’s topic, I hope we all learn new things. 

Always remember to smile! bitter or sweet. J