Wednesday, 1 April 2015

Basics of Linked Lists in C++

Basics of Linked Lists in Cpp with code examples:

A linked list is a data structure consisting of a group of nodes which together represent a sequence. Linked lists are used to store collections of data. The specific type of element is not important since essentially the same structure works to store elements of any type.

Each node is composed of a data and a reference to the next node in the sequence. More complex variants add additional links. Each node contain two fields: an integer value and a link to the next node.

The last node is linked to a null terminator used to signify the end of the list.



Advantages of the linked lists:

Dynamic allocation of needed memory while the program is running is one of the great advantage for linked lists.
Node insertion and deletion is very easy using the linked lists
Linear data structures such as stacks and queues are easily executed with a linked list.
Linked lists can reduce access time.

Disadvantages:

They may use more memory due to pointers requiring extra storage space.
Nodes in a linked list must be read in order from the beginning as linked lists are inherently sequential access.
The nodes are stored in contiguously; this will take more time to access individual elements within the list.

Single linked list:

Singly linked lists contain nodes, which have a data field as well as a 'pointer' field, which points to the next node.

Possible operations on Single linked list:


typedef struct stNode
 {
    int idata; // The data being stored in the node
    stNode next // A reference to the next node, null for last node
 }
 typedef struct stList
 {
     stNode firstNode // points to first node of list; null for empty list
 }

Traversal of a singly linked list is simple, beginning at the first node and following each next link until we come to the end:

 stNode:= stList.firstNode
 while stNode not null
      // your code block
     stNode:= stNode.next

The following code inserts a node after an existing node in a singly linked list. The diagram shows how it works. Inserting a node before an existing one cannot be done directly; instead, one must keep track of the previous node and insert a node after it.

Pseudo code for InserLater function:

function InsertLater(stNode ostnode, stNode ostnewNode) // insert ostnewNode after node
     ostnewNode.next := ostnode.next
     ostnode.next    := ostnewNode










Inserting at the beginning of the list requires a separate function. This requires updating firstNode.

Pseudo code for InsertFirst function:

/*insert node before current first node*/
 function InsertFirst (stList ostlist, stNode ostnewNode)
  ostnewNode.next   := ostlist.firstNode
     ostlist.firstNode := ostnewNode


For removing the node after a given node, and for removing a node from the beginning of the list I have provided some pseudo code below.

Pseudo code for RemoveLater function:

function RemoveLater(stNode ostnode) // remove node past this one
     obsoleteNode := ostnode.next
     ostnode.next := ostnode.next.next
     destroy obsoleteNode

Pseudo code for RemoveFirst function:

 function RemoveFirst (stList ostlist) // remove first node
     obsoleteNode := ostlist.firstNode
     ostlist.firstNode := ostlist.firstNode.next // point past deleted node
     destroy obsoleteNode


The below diagram helps us to find and remove a particular node.


Double linked list:

Each node contains   besides the next-node link, a second link field pointing to the 'previous' node in the sequence. The two links may be called 'next node' and 'previous node'.

A doubly linked list whose nodes contain three fields: a data value, the pointer to the next node, and the pointer to the previous node

Circular Linked list:

The last node of the pointer is connected to the first node, in that case the list is said to be 'circular' or 'circularly linked'; otherwise it is said to be 'open' or 'linear'.
Circular linked lists

In the case of a circular doubly linked list, the only change that occurs is that the end, of the said list is linked back to the front of the list and vice versa.

Circularly linked list:

In a circularly linked list, all nodes are linked in a continuous circle, without using null. For lists with a front and a back (such as a queue), one stores a reference to the last node in the list. The next node after the last node is the first node. Elements can be added to the back of the list and removed from the front in constant time.

Circularly linked lists can be implemented for singly or doubly linked lists.

Assuming that TempNode is some node in a non-empty circular singly linked list, this code iterates through that list starting with TempNode:

Pseudo code for Finding the required node I the linked list:

function SearchNode(TempNode)
   if TempNode ≠ null
     ostNode:= TempNode
     do
       do something with ostNode.value
       ostNode := ostNode.next
     while ostNode ≠ TempNode

Notice that the test "while ostNode ≠ TempNode" must be at the end of the loop.
This function inserts a node " TempNode " into a circular linked list after a given node "node". If "node" is null, it assumes that the list is empty.

function InsertLater(stNode ostnode, stNode TempNode)
     if ostnode = null
       TempNode.next := TempNode
     else
       TempNode.next := ostnode.next
       ostnode.next := TempNode

Suppose that " ostNode " is a variable pointing to the last node of a circular linked list. To append " TempNode " to the end of the list, we have to do.
 
InsertLater(ostNode, ostnewNode)
 ostNode := ostnewNode

To insert " ostnewNode " at the beginning of the list, we have to do
 InsertLater(ostNode, ostnewNode)
 If ostNode = null
   ostNode := ostnewNode


No comments: