Tag: linear data structure

Data Structures: Stack

A Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO (Last In First Out) or FILO (First In Last Out).

Diagram: Stack

Push: Insert an element on to the top of the stack.

Pop: Delete the topmost element and return it.

Furthermore, the following additional functions are provided for a stack in order to check its status.

  • Peek: Return the top element of the stack without deleting it.
  • isEmpty: Check if the stack is empty.
  • isFull: Check if the stack is full.

Applications of stacks

  • Used for expression evaluation (e.g.: shunting-yard algorithm for parsing and evaluating mathematical expressions).
  • Used to implement function calls in recursion programming.

Data Structures: Linked List

Like arrays, the Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at a contiguous location; the elements are linked using pointers.

Like arrays, the Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at a contiguous location; the elements are linked using pointers.

Diagram: Linked List

Why use a Linked List over an Array?

Arrays can be used to store linear data of similar types, but arrays have the following limitations:
1) Arrays have a fixed size – so we must know the upper limit (ceiling) on the number of elements in advance. Additionally, in most implementations, the memory allocation is equal to the upper limit regardless of usage. 
2) Inserting new elements into an array is expensive because space has to be created for the new elements and to create space, existing elements have to be shifted. 
For example, in a system, if we maintain a sorted list of IDs in an array nums[]. 
nums[] = [100, 101, 105, 200, 206]. 
And if we want to insert a new ID 104, then to maintain the sorted order, we have to move all the elements after 100 (excluding 100). 
Deletion is also expensive with arrays. For example, to delete 101 in nums[], everything after 101 has to be shifted.

Advantages over arrays:

  • Dynamic size 
  • Ease of insertion/deletion

Disadvantages:

  • Random access is disallowed. We must access elements sequentially starting from the first node and then traverse the list until we reach the element we are seeking. So an efficient binary search is not an option with linked lists in their default implementation.
  • The more segments a list is broken into the more overhead there is for locating the next linked element.
  • Extra memory space for a pointer is required with each element of the list.
  • Not cache friendly. Since array elements are contiguous locations, there is locality of reference which is not the case for linked lists.

Representation

A linked list is represented by a pointer to the first node of the linked list. The first node is called the head. If the linked list is empty, then the value of the head is NULL. 
Each node in a list consists of at least two parts: 
1) Data 
2) Pointer (Or Reference) to the next node