Data Structure - Unit I - ABSTRACT DATA TYPES (ADT)

 

ABSTRACT DATA TYPES (ADT) AND LISTS

1. ABSTRACT DATA TYPES (ADT)

An Abstract Data Type (ADT) is a logical specification of a data type which defines:

  • The data objects
  • The operations that can be performed on those objects

ADT does not specify the implementation details. It only describes what operations are allowed, not how they are carried out.

 

Need for ADT

  • To separate logic from implementation
  • To improve software reliability
  • To support data abstraction

 

Components of ADT

  1. Data – Values stored
  2. Operations – Actions on data
  3. Interface – Interaction with user/program

 

ADT Operations:

  • Create()
  • Insert(position, element)
  • Delete(position)
  • Search(element)
  • Traverse()

 

Advantages of ADT

  • Implementation independent
  • Easier debugging
  • Improves modularity
  • Supports code reusability

 

2. LIST ADT

A List ADT is a linear collection of elements arranged in a sequential order, where:

  • Each element has a unique position
  • Duplicate elements are allowed

 

Characteristics

  • Linear structure
  • Ordered elements
  • Dynamic or static size

 

Operations of List ADT

  1. Creation
  2. Insertion
  3. Deletion
  4. Searching
  5. Traversal
  6. Merging

3. ARRAY-BASED IMPLEMENTATION OF LIST ADT

Memory Representation

  • Uses contiguous memory
  • Accessed using index

Example:

Index: 0  1  2  3

Data : 10 20 30 40

 

Insertion Algorithm

  1. Check overflow
  2. Shift elements to the right
  3. Insert element

 

Deletion Algorithm

  1. Check underflow
  2. Shift elements to the left
  3. Reduce size

 

MERGE OPERATION IN LIST

Combining two lists into a single list.

Sorted Merge Algorithm

  1. Compare first elements
  2. Insert smaller element
  3. Move pointer
  4. Repeat until end

 

TRAVERSAL OF LIST

Visiting every element once.

Traversal Algorithm

  1. Start from head
  2. Print data
  3. Move to next
  4. Stop at NULL / first node

 

 

APPLICATIONS OF LISTS

  1. Polynomial manipulation
  2. Dynamic memory allocation
  3. Operating systems
  4. Undo/Redo operations
  5. Music playlist

 

Advantages

  • Faster access
  • Simple structure
  • Efficient traversal

 

Disadvantages

  • Fixed size
  • Memory wastage
  • Costly insert/delete

4. LINKED LIST IMPLEMENTATION OF LIST ADT

Definition

A linked list is a dynamic linear data structure consisting of nodes, where:

  • Each node contains data
  • Each node has link(s) to other nodes

 

4.1 SINGLY LINKED LIST

Node Structure

| Data | Next |

 

Insertion Operations

Insertion at Beginning

  1. Create new node
  2. Set new->next = head
  3. Update head

 

Insertion at End

  1. Traverse to last node
  2. Set last->next = new
  3. new->next = NULL

 

Deletion Operations

Delete First Node

  1. temp = head
  2. head = head->next
  3. free(temp)

 

Delete Last Node

  1. Traverse to second last
  2. Set next = NULL
  3. Free last node

 

Advantages

  • Dynamic size
  • Efficient insert/delete
  • No memory wastage

 

Disadvantages

  • Extra memory for pointer
  • No backward traversal

4.2 CIRCULAR LINKED LIST

Definition

A circular linked list is a linked list in which:

  • Last node points to the first node
  • No NULL pointers

 

Diagram (Representation)

[10] → [20] → [30]

  ↑               ↓

  ←–––––––––––––––

 

Advantages

  • No NULL pointer checks
  • Efficient traversal
  • Suitable for round-robin scheduling

 

Applications

  • CPU scheduling
  • Multiplayer games
  • Buffer management

4.3 DOUBLY LINKED LIST

Node Structure

| Prev | Data | Next |

 

Insertion

  • Insert at beginning
  • Insert at end
  • Insert at position

 

Deletion

  • Easy deletion of any node
  • No need for previous node traversal

 

Advantages

  • Bidirectional traversal
  • Efficient deletion

 

Disadvantages

  • Extra memory
  • Complex implementation

 

5. POLYNOMIAL MANIPULATION USING LINKED LIST

Polynomial Representation

Each node stores:

| Coefficient | Exponent | Next |

Example:

5x³ + 4x² + 3

 

5.1 Polynomial Insertion

Algorithm:

  1. Create node
  2. Compare exponents
  3. Insert in descending order
  4. Combine like terms

 

5.2 Polynomial Deletion

Steps:

  1. Traverse list
  2. Locate exponent
  3. Adjust links
  4. Free node

 

5.3 Polynomial Traversal

Steps:

  1. Start from head
  2. Print coefficient and exponent
  3. Move to next

 

5.4 Polynomial Addition (Merge Operation)

Algorithm

  1. Compare exponents of two polynomials
  2. If same, add coefficients
  3. Insert result into new list
  4. Copy remaining terms

 

5.5 Polynomial Multiplication

Algorithm

  1. Multiply each term of P1 with P2
  2. Insert into result list
  3. Combine like terms

 

 

 

Comments

Post a Comment

Popular posts from this blog

PYTHON PROGRAMMING (23UCSCC01) – UNIT - III

Image
  PYTHON PROGRAMMING ( 23UCSCC01 ) – UNIT - III Functions: Function Definition – Function Call – Variable Scope and its Lifetime- Return Statement. Function Arguments : Required Arguments, Keyword Arguments, Default Arguments and Variable Length Arguments- Recursion. Python Strings: String operations- Immutable Strings - Built-in String Methods and Functions - String Comparison. Modules : import statement- The Python module – dir() function – Modules and Namespace – Defining our own modules.   What is a Function in Python? A function is a block of reusable code that performs a specific task. It helps us organize code into small, manageable parts, avoid repetition, and improve clarity. Benefits of Using Functions: ·          Modularity:  Breaking down complex problems into smaller, manageable parts. ·          Reusability:  Avoiding repetitive code by defining a task once an...
Read more

Data Structure

Image
  Data Structure Stack   A stack is a linear data structure that follows the LIFO (Last In, First Out) principle. That means the last element inserted is the first one to be removed.   Characteristics Linear data structure Follows LIFO order Supports insertion and deletion from only one end called the top Efficient for managing recursive function calls, undo operations, etc.   Basic Operations on Stack Operation Description push(x) Inserts an element x on top of the stack pop() Removes the top element of the stack peek() / top() Returns the top element isEmpty() Checks if the stack is empty isFull() Checks if the stack is full (for fixed size array implementation)     Stack Representation Stacks can be implemented in two ways: Using Arrays Using Linked Lists ...
Read more

PYTHON PROGRAMMING - LAB EXERCISES (23UCSCCP01)

PYTHON PROGRAMMING  LAB       Ex.No: 01     Program using variables, constants, I/O statements in Python Date:       Aim:   To write a Python program using variables, constants, input, and output statements.     Algorithm:   1. Start the program 2. Define a constant PI 3. Get the radius of the circle 4. Calculate the area using the formula:             area = PI *radius * radius 5. Display the calculated area value 6. End the program     #Program using variables, constants, I/O statements in Python   # Constant: Pi value (usually written in uppercase) PI = 3.14159   # Input: Read radius from user radius = float(input("Enter the radius of the circle (in meters): "))   # Variable: Calculate area using formula area = PI ...
Read more