Scribd
Upload
28 views5 pages

Data Structures 11 Mark Notes

The document provides an overview of various data structures in C, focusing on self-referential structures, dynamic memory allocation, and linked lists (singly, doubly, and circular). It outlines their definitions, advantages, disadvantages, and applications, emphasizing their roles in dynamic memory usage and data management. Key operations for linked lists and common errors in dynamic memory allocation are also discussed.

Uploaded by

archuanisha
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
28 views5 pages

Data Structures 11 Mark Notes

The document provides an overview of various data structures in C, focusing on self-referential structures, dynamic memory allocation, and linked lists (singly, doubly, and circular). It outlines their definitions, advantages, disadvantages, and applications, emphasizing their roles in dynamic memory usage and data management. Key operations for linked lists and common errors in dynamic memory allocation are also discussed.

Uploaded by

archuanisha
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Data Structures using C - 11 Mark Notes

1. Self-Referential Structures

A self-referential structure is a structure that includes a pointer to an instance of the same structure type.

Example:

struct node {

int data;

struct node *next;

};

- Used to create dynamic data structures like linked lists, trees, etc.

- Enables recursive referencing.

- Memory Representation: |data|next ->|data|next ->|data|NULL

- Advantages: Dynamic memory usage, better modular code, supports recursive structures.

2. Dynamic Memory Allocation

Dynamic memory allocation allows memory to be allocated at runtime using functions from stdlib.h.

Functions:

- malloc(): Allocates uninitialized memory

- calloc(): Allocates and initializes memory

- realloc(): Resizes previously allocated memory

- free(): Deallocates memory

Example:

int *ptr = (int *)malloc(5 * sizeof(int));

if(ptr == NULL) printf("Memory not allocated");

else printf("Memory allocated");


Data Structures using C - 11 Mark Notes

- Prevents memory wastage, flexible sizing.

- Common Errors: memory leaks, dangling pointers, double free errors.

3. Singly Linked List

A linear data structure where each node contains data and a pointer to the next node.

struct node {

int data;

struct node *next;

};

Operations:

- Insertion (begin, middle, end)

- Deletion

- Traversal

- Searching

Advantages:

- Dynamic memory usage

- Simple structure

- Easy insertion/deletion

Disadvantages:

- No backward traversal

- Sequential access only


Data Structures using C - 11 Mark Notes

4. Doubly Linked List

Each node contains data, a pointer to the previous node, and a pointer to the next node.

struct node {

int data;

struct node *prev;

struct node *next;

};

Features:

- Bidirectional traversal

- Efficient insert/delete from both ends

Applications:

- Browsers (back/forward)

- Undo operations

Advantages:

- More flexibility

Disadvantages:

- More memory usage

- Complex pointer management

5. Circular Linked List

In a circular linked list, the last node points to the first node forming a loop.

Types:
Data Structures using C - 11 Mark Notes

- Singly Circular

- Doubly Circular

Uses:

- Round-robin scheduling

- Music playlists

- Multiplayer games

Advantages:

- No NULL at end

- Continuous looping

Disadvantages:

- Careful handling needed during traversal and deletion

6. Applications of Linked Lists

1. Stack: Implemented using singly linked list (push/pop).

2. Queue: Implemented using singly linked list (enqueue/dequeue).

3. Polynomial Representation: Each term is a node.

4. Adjacency List: Graph representation.

5. Memory Management: Free lists in OS.

6. Browser History: Doubly linked list for forward/backward.

Comparison:

| Application | Type of List |

|-------------------|--------------|

| Stack | Singly |

| Deque | Doubly |
Data Structures using C - 11 Mark Notes

| Round-Robin | Circular |

| Graph | Singly |

| Undo in Editors | Doubly |

You might also like