Abstract Data Type (ADT)

Defines a data structure by its behavior from the user's perspective, rather than its concrete implementation. ADT is a collection of data and a set of operations on those data.
Examples: Stack, Queue, Linked List

Stack

• A list operating on the Last In First Out principle (LIFO)
• Push: Adding item to stack
• Pop: Removing item from the stack
• isEmpty: Checks if stack is empty
• The first item added to the stack is the last item that can be removed
• Implementing stack using array
  • Declare an array to store the contents of stack
  • Declare a stack pointer pointing to the index of last element added (Value -1 if stack is empty)
• Uses: Managing function calls, Syntax parsing in compilers, Recursion, 'Undo' functions, System memory architecture, Browsing history, Expression parsing (Reverse Polish Notation)
• Advantage: Simple, Efficient, Limited Memory, LIFO
• Disadvantage: Limited access, Random access not possible, Limited capacity leading to overflow

Queue

• A list operating on the First In First Out principle (FIFO)
• The first item added is the first item to be removed
• Data is added from the rear end by using the EndPointer/TailPointer and removed from the front by using the StartPointer/HeadPointer
• Enqueue: Add an element to the back of the queue.
• Dequeue: Remove the element at the front of the queue.
• isEmpty: Check if the queue is empty.
• Applications: Task Scheduling in OS and printer, Handling request in web server, streaming, call centers, handling packets, messaging or ordering services, video or mp3 players, traffic management, physical queues like supermarket

• Advantages: Large data managed efficiently, multi user services
• Disadvantages: Operations on middle elements are hard, maximum size defined before implementation

Linked List

• Nodes: Basic data structure which contains data and one or more links/pointers to other nodes. Nodes can be used to represent a tree structure or a linked list.
  • Node’s successor is the next node
  • Node's predecessor is the previous node
• Pointers: Variable that stores the memory address of another variable as its value
• A linked list is a data structure used to store a collection of items where each item is linked to the next one using pointers.
• Traverse a linked list: Start at the first node and then go from node to node, following each node’s pointer to find the next node.
• Two types depending on how data is sorted: ordered and unordered.
• Linked List can be implemented using 2D Arrays (Singly)
  • The arrays are for data and the other for pointers
• Advantage: Fast insertion and deletion
• Disadvantage: Slow Search