02 Data Structures

Data Structures

Array

• Sequence of items of the same data type (homogenous)
• Items can be accessed, retrieved, stored or replaced at given index positions
• Physical Size: total number of array cells
• Logical Size: number of items currently in it
• Insertion
• 
  • 
• Removal
• 
  • 

Linked List

Describe

• Each element/node contains data and a pointer to the next element
• The last element has a null pointer signifying the end of the list
• There is a head pointer pointing to the first element of the list
• Noncontiguous
• Basic representation is a node

Advantages	Disadvantages
Dynamic size (can grow and shrink)	Require traversal -> **slower **to read or change, while fixed-sized arrays allows direct access
More space-efficient (only required space used to store data)	More **complex **to implement and manage, while arrays are simpler and straightforward to use
Insertion and deletion more efficient (do not require shifting elements like arrays)	Additional **memory **per node for storing pointer (or reference) to next node

Node class

Traverse linked list

Searching

Accessing ith tem

Insert into linked list

Deletion from linked list

Stack

• LIFO data structure
• Restricted to one end called the top

Infix and postfix

• Converting infix to postfix

  • Start with empty postfix expression and empty stack
  • Stack will hold operators and left parentheses
  • Scan across infix expression from left to right
  • On encountering operand, append to postfix expression
  • On encountering open bracket, push to stack
  • On encountering an operator, pop off the stack all operators with equal or higher precedence, append to postfix expression and push scanned operator onto stack
  • on encountering closed bracket, pop operators from stack to postfix expression until meeting the matching open bracket, which is discarded
  • on encountering end of infix expression, pop remaining operators from stack to the postfix expression

• Evaluating postfix

  • Scan across the postfix operation from left to right
  • On encountering operator, apply it to two preceding operands; replace all three by the result
  • Continue scanning until end of expression

Stack Memory Management

When a subroutine (function or method) is called, an activation record is created to store the current environment for that function (including parameters, local/temp variables, return address and return value)

When a function calls another function, it interrupts its own execution and needs to be able to resume its execution in the state it was in when it was interrupted

The order of return of functions is LIFO. We use a stack to store the activation records

**When a function is called **

1. Push copy of activation record onto run-time stack
2. Copy arguments into parameter spaces
3. Transfer control to the starting address of the body of the function

Top activation record is of the function currently being executed

When function terminates

1. Pop activation record of terminated function from run-time stack
2. Use new top activation record to restore the environment of the interrupted function and resume execution of the interrupted function

Run-time stack with activation records for a recursive power function

Implementation of stack

Using array

Using linked list

• **top **points to the list’s head
• Pushing and popping are accomplished by adding and removing nodes at the head of the list

Queues

• Insertions restricted to one end called the rear
• Removals restricted to one end called the front
• FIFO
• enqueue and dequeue

Queue implementation

Using array

Linear array queue

**Circular array queue **

Using linked list