Linked List and Stack and Queue

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.

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.

 2.  Remove nodes.

To remove a node we con do popHead or popTail.

• 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. 

STACK AND QUEUE

From my last post, I’ve talked about single linked list and double linked list, now we’re going to talk about STACK AND QUEUE. Both stack and queue is a linear data structure. Queues and stacks are also complementary in the actual use scenarios.

So what is the difference between stack and queue? 

In STACK the elements can be inserted and deleted only from one side of the list called the TOP and a stack follows the LIFO (Last In, First Out) principle, so the element inserted at the last is the first element to come out. In stack if you want to add a new node you can do push like in a single linked list and do pop if you want to remove a node. But remember that the added new node will be put on top or say at the end of the list and if you do pop or remove a node the one that will be removed will be the top or the recently added node. One of the applications for stack is an undo mechanism in a text editor.

Here is a visualization of stack.

For QUEUE the elements can be inserted only from one side of the list called REAR(the last inserted element), and the elements can be deleted only from the other side called the FRONT(the first and still element of the list) and a queue follows the FIFO (First In, First Out) principles, so the elements inserted at first in the list will be the first to be removed from the list. In queue adding a new node--to the end of the list is called enqueue and removing the front node is called dequeue. Queue will be very useful when doing parsing or converting arithmetic expressions from infix to postfix.

Here is a visualization of queue.

That’s it for my brief summary for stack and queue, I hope we all learn something from this. 

Have a nice day!! Bitter or sweet J