Stacks

A stack is an ordered dynamic linear list in which all additions of new elements and deletions of existing elements are restricted to one end, called the Top. If a data series is inserted into a stack, and then removed it, the order of the data would be reversed. This reversing attribute due to addition and removal at the top of stack give a special behaviour, called as “Last-in, first-out” (LIFO) structure.

A stack is dynamic because it is constantly changing objects, it expands and shrinks with passage of time.

The basic Stack operations are Create Stack, Push, Pop, Stacktop, Emptystack, Full stack, Stack Counts,

And Destroy stacks.

We shall also study the following application of stacks, reversing data (convert decimal to

binary) parsing data (matching of parentheses in source programs), postponing data usage (Infix, Postfix, Prefix and evaluation of Postfix expressions.) Stack frames concept is studied in a separate chapter on recursion.

Doubly Linked List Deletion

Deleting from a doubly linked list requires that the deleted node’s predecessor, if any, be pointed to the deleted node’s successor and that the successor, if any, be set to point to the predecessor. This rather straight forward logic is shown in Figure 21. Once we locate the node to be deleted, we simply change its predecessor’s and successor’s pointers and recycle the node.

The pseudocode is shown in Algorithm 13.

Algorithm – 13 Double linked list delete

algorithm deleteDbl (ref list ,

val pDlt ,

ref dataout )

The algorithm deletes a node from a doubly linked list.

Pre list is metadata structure to a valid list

pDlt is a pointer to the node to be deleted

Post node deleted

1 dataout = pDlt->data

Check if not first node

2 if (pDlt->back not null)

Point predecessor to successor

1 pPred = pDlt->back

2 pPred->fore = pDlt->fore

3 else (First node)

Update head pointer

1 list.head = pDlt->fore

4 end if

Check if not last node

5 if (pDlt->fore not null)

Point successor to predecessor

1 pSucc = pDlt->fore

2 pSucc->back = pDlt->back

6 else (Last node)

Point rear to predecessor

1 list.rear = pDlt->back

7 end if

8 recycle (pDlt)

9 list.count = list.count - 1

10 return

end deleteDbl

Other Linked List Variations

We introduce two other useful linked list variations – the circularly linked list and the doubly linked list.

Circularly linked list

In the circularly linked list, the last node’s link points to the first node of the list, as shown in Figure 18. Circularly linked list are primarily used in structures that allow access to nodes in the middle of the list without starting at the beginning. In circular list, nodes form a ring: The list is finite and each node has a successor.

Insertion and deletion into a circularly linked list follow the same logic used in singly linked list except that the last node points to the first node. Therefore, when inserting and deleting the last node, in addition to updating the rear pointer in the header, we must also point the head field to the first node.

Given that we can directly access a node in the middle of the list through its data structure, we are then faced with a problem when searching the list. If the search target lies before the current node, how do we find it? In a singly linked list, when we arrive at the end of the list the search is complete. In a circular list, however we automatically continue the search from the beginning of list.

The ability to continue the search presents another problem. What if the target does not exist? In the singly linked list, if we did not find the data we are looking for, we stopped when we hit the end of list. With a circular list, we save the starting node’s address and stop when we have circled around to it, as shown code below.

Loop (key not equal to pLoc->node.data

AND pLoc->link not equal to startAddress)

Circular list, in which the last node is followed by the first node, is usually preferable to non-circular one, for two reasons:

• They provide easy access to both ends of a list: notice that we do not need the first pointer in the header, because we can easily reach the first node with rear -> link -> data
• the code for processing a circular list is often simpler than the code for processing a non-circular list - mainly because you don't have to constantly check if the next node is defined - it is always defined.

At the implementation level, however, circularity does create one very tricky case that is a very common source of bugs, and that is singleton lists. When there is only one node in a circular list, it points to itself as the next node.

Doubly Linked or Two-way Linked Lists

One of the most powerful variations of linked lists is the doubly linked list. A doubly linked list is a linked list structure in which each node has a pointer to both its successor and its predecessor. Figure 19 is a representation of a doubly linked list.

There are three pieces of metadata in the head structure: a count, a head pointer, and a rear pointer. Although a rear pointer is not required in all doubly linked lists, it makes some of the list algorithms, such as insert and search, more efficient.

Each node contains two pointers, a backward pointer to its predecessor and a forward pointer to its successor. In Figure 19 these pointers are designated B and F, respectively.

Another variation on the doubly linked list is the doubly linked circularly linked list. In this variation, the last forward pointer points to the first node of the list and the backward pointer of the first node points to the last node. If there is only one node in the list, both the forward and backward pointers point to the node itself.

Doubly Linked List Insertion

Inserting a node into a doubly linked list follows the basic pattern of inserting a node into a singly linked list, but we also need to connect both the forward and backward pointers.

A null doubly linked list’s head and rear pointers are null. To insert a node into a null list, we simply set the head and rear pointers to point to the new node and set the forward and backward pointers of the new node to null. The results of inserting a node into a null list are shown in Figure 20(a).

Figure 20(b) shows the case for inserting between two nodes. The new node needs to be set to point to both its predecessor and its successor, and they need to be set to point to the new node. Because the insert is in the middle of the list, the head structure is unchanged except for adding to the count.

Inserting at the end of the list requires that the new node’s back pointer be set to point to its predecessor. Because there is no successor, the forward pointer is set to null. The rear pointer in the head structure must also be set to point to the new rear node.

Algorithm 22 contains the code to insert a node into a doubly linked list.

Algorithm – 12 Doubly linked list insert

algorithm insertDbl (ref list ,

pPre ,

pSucc ,

val dataIn )

This algorithm inserts data into a doubly linked list.

Pre list is metadata structure to a valid list

PPre is pointer variable for predecessor

PSucc is pointer variable for successor

dataIn contains the data to be inserted

Post The data have been inserted in sequence

Return 0 : failed—dynamic memory overflow

1 : successful

1 if (full list)

1 return 0

2 end if

3 allocate (pNew)

4 pNew->data = dataIn

Locate insertion point in list

5 if (pPre is null)

Inserting before first node or into empty list

1 pNew->back = null

2 pNew->fore = list.head

3 list.head = pNew

6 else

Inserting into middle or end of list

1 pNew->back = pPre

2 pNew->fore = pPre->fore

3 pPre->fore = pNew

7 end if

Test for insert at end of list and also check not empty list

8 if (pPre->fore null and pPre not null)

Inserting at end of list –set rear pointer

1 list.rear = pNew

9 else

Inserting in middle of list — point successor to new

1 if (pSucc not null) check not empty list

1 pSucc->back = pNew

10 end if

11 list.count = list.count + 1

12 return(1)

end insertDbl

Operation 13 – Print List:

One of the more common uses of link list traversals is to print the entire contents of a list. If the user selects the print list option from the menu, we traverse the list and print all of the key fields. In this program, we simply print a sequential number and the data from the node Within a loop, we continue until all of the data have been printed. The code is shown in Algorithm 11.

Algorithm 13: Print Linked List

algorithm printList (val list )

This algorithm traverses a linked list and prints the data in node.

Pre list is metadata structure to a valid list

Post All data have been printed in sequence

1 if (list.head null)

1 Print (No data in list.)

2 else

1 print (**** Begin Data Print ****)

2 sno = 0

1 dataptr = list.head

2 loop (dataptr-> link not null)

1 sno = sno + 1

2 print (sno, dataPtr->data)

3 dataptr = dataptr-> link

5 end loop

6 print (**** End Data Print ****)

3 end if

4 retrun

end printList

Operation 12 – Destroy List:

When a list is no longer needed but the application is not done, the list should be destroyed. Destroy list deletes any nodes still in the list and recycles their memory. It then sets the metadata to a null list condition. The code for destroy list is shown in Algorithm 10.

Algorithm – 10 Destroy linked list

algorithm destroyList (ref list )

Deletes all data in list

Pre list is metadata structure to a valid list

Post All data deleted

1 loop (list.count not zero)

1 dltPtr = list.head

2 list.head = dltPtr->link

3 list.count= list.count – 1

4 recycle (dltPtr)

2 end loop

No data left in list. Reset metadata.

3 list.head = null

4 return

end destroyList

Operation 9 – Traverse List :

Algorithm that traverse a list start at the first node and examine each node in succession until the last node has been processed. Traversal logic is used by several different types of algorithms, such as changing a value in each node, printing the list, summing a field in the list, or calculating the average of a field. Any application that requires that the entire list be processed uses a traversal.

To traverse the list we need a walking pointer, a pointer that moves from node to node as each element is processed. Assuming a linked list with a head structure, the following pseudocode uses a walking pointer to traverse the list. Each loop modifies the pointer to move to the next node in sequence as we traverse the list.

pos = list.head

loop (pos not null)

process (pos->data)

pos = pos->link

We begin by setting the walking pointer to the first node in the list. Then, using a loop, we continue until all of the data have been processed. Each loop calls a process module and passes it the data and then advances the walking pointer to the next node. When the last node has been processed, the walking pointer becomes null and the loop terminates.

Because we need to remember where we are in the list from one call to the next, we need to add a current position pointer to the head structure. It keeps track of the node processed after the last call. The head structure is shown in Figure 17. The figure also shows how the position pointer is modified to move from one node to the next as the traversal algorithm is called.

Each call also needs to know whether we are starting from the beginning of the list or continuing from the last node processed. This information is communicated through the parameter list. The basic logic to traverse a list is

shown in Algorithm 9. We name it getNext because it is called to get the next node in the traversal.

Algorithm – 9 Traverse linked list

algorithm getNext (ref list ,

val fromWhere ,

ref dataOut )

Traverses a linked list. Each call returns the location of an element in the list.

Pre list is metadata structure to a valid list

fromWhere is 0 to start at the first element

fromWhere is 1 to continue from current position

dataOut is variable to receive data

Post dataOut contains data and true returned

-or- if end of list, returns false

Return true if next element located, false if end of list

1 if (fromWhere is 0)

Start from first

1 if (list.count is zero)

1 success = false

2 else

1 list.pos = list.head

2 dataOut = list.pos->data

3 success = true

3 end if

2 else

Continue from pos

1 if (list.pos->link equal null)

End of List

1 success = false

2 else

1 list.pos = list.pos->link

2 dataOut = list.pos->data

3 success = true

3 end if

3 end if

4 return success

end getNext

Operation 8 – List Count/Size:

List count is another simple, one-line module. It is necessary because the calling module has no direct access to the list structure. Its implementation is shown in Algorithm 8.

Algorithm – 8 Linked list count

algorithm listCount (val list )

Returns integer representing number of nodes in list.

Pre list is metadata structure to a valid list

Return count for number of nodes in list

1 return (list. count)

end listCount