Self-Referential structures

Self-Referential structures are those structures that have one or more pointers which point to
the same type of structure, as their member.

In other words, structures pointing to the same type of structures are self-referential in nature.
struct node {
int data1;
char data2;
struct node* link;
};

int main()
{
struct node ob;
return 0;
}

In the above example ‘link’ is a pointer to a structure of type ‘node’. Hence, the structure
‘node’ is a self-referential structure with ‘link’ as the referencing pointer.
An important point to consider is that the pointer should be initialized properly before
accessing, as by default it contains garbage value. (Link is pointer member that points to a
structure of the same types as the one being declared. Is referred to as a link. Link can tie
one node to another node.)

Types of Self-Referential Structures

1. Self-Referential Structure with Single Link
2. Self-Referential Structure with Multiple Links
Self-Referential Structure with Single Link: These structures can have only one self-
pointer as their member. The following example will show us how to connect the objects of
a self-referential structure with the single link and access the corresponding data members.
The connection formed is shown in the following figure.

#include <stdio.h>

struct node {
int data1;
char data2;
struct node* link;
};

int main()
{
struct node ob1; // Node1

// Initialization
ob1.link = NULL;
ob1.data1 = 10;
ob1.data2 = 20;

struct node ob2; // Node2

// Initialization
ob2.link = NULL;
ob2.data1 = 30;
ob2.data2 = 40;

// Linking ob1 and ob2

ob1.link = &ob2;

// Accessing data members of ob2 using ob1

printf("%d", ob1.link->data1);
printf("\n%d", ob1.link->data2);
return 0;
}

Output
30
40
Self-Referential Structure with Multiple Links: Self-referential structures with multiple
links can have more than one self-pointer. Many complicated data structures can be easily
constructed using these structures. Such structures can easily connect to more than one node
at a time. The following example shows one such structure with more than one links.
The connections made in the above example can be understood using the following figure.

#include <stdio.h>

struct node {
int data;
struct node* prev_link;
struct node* next_link;
};

int main()
{
struct node ob1; // Node1

// Initialization
ob1.prev_link = NULL;
ob1.next_link = NULL;
ob1.data = 10;

struct node ob2; // Node2

// Initialization
ob2.prev_link = NULL;
ob2.next_link = NULL;
ob2.data = 20;

struct node ob3; // Node3

// Initialization
ob3.prev_link = NULL;
ob3.next_link = NULL;
ob3.data = 30;

// Forward links
ob1.next_link = &ob2;
ob2.next_link = &ob3;
 // Backward links
ob2.prev_link = &ob1;
ob3.prev_link = &ob2;

// Accessing data of ob1, ob2 and ob3 by ob1

printf("%d\t", ob1.data);
printf("%d\t", ob1.next_link->data);
printf("%d\n", ob1.next_link->next_link->data);

// Accessing data of ob1, ob2 and ob3 by ob2

printf("%d\t", ob2.prev_link->data);
printf("%d\t", ob2.data);
printf("%d\n", ob2.next_link->data);

// Accessing data of ob1, ob2 and ob3 by ob3

printf("%d\t", ob3.prev_link->prev_link->data);
printf("%d\t", ob3.prev_link->data);
printf("%d", ob3.data);
return 0;
}

Output
10 20 30
10 20 30
10 20 30

In the above example we can see that ‘ob1’, ‘ob2’ and ‘ob3’ are three objects of the self-
referential structure ‘node’. And they are connected using their links in such a way that any
of them can easily access each other’s data. This is the beauty of the self-referential
structures. The connections can be manipulated according to the requirements of the
programmer.

Applications: Self-referential structures are very useful in creation of other complex data
structures like:
• Linked Lists
• Stacks
• Queues
• Trees
• Graphs etc.
 Dynamic memory allocation in Data Structure

Dynamic memory allocation is a fundamental concept in data structures and programming. It

allows programs to allocate memory at runtime, providing flexibility and efficiency when
working with data structures of varying sizes.

Understanding Dynamic Memory Allocation

In most programming languages, including C++, memory can be classified into two categories:
stack memory and heap memory. Local variables and function calls are stored in the stack
memory, whereas the more adaptable heap memory can be allocated and released at runtime.

The process of allocating and releasing memory from the heap is known as dynamic memory
allocation. It allows the programmer to manage memory explicitly, providing the ability to
create data structures of varying sizes and adjust memory requirements dynamically.

Why would we need to allocate memory while the program is executing? Because, even
though it isn’t blatantly visible, not being able to allocate memory during run time precludes
flexibility and compromises with space efficiency. Specially, those cases where the input
isn’t known beforehand, we suffer in terms of inefficient storage use and lack or excess of
slots to enter data (given an array or similar data structures to store entries). So, here we
define Dynamic Memory Allocation: The mechanism by which storage/memory/cells can
be allocated to variables during the run time is called Dynamic Memory Allocation.
Dynamic Memory Allocation Techniques:

In most programming languages, dynamic memory allocation is achieved through dedicated

functions provided by the language or standard library. Let's explore three commonly used
techniques:

1. malloc:

The malloc (memory allocation) function is used to allocate a specified number of bytes in
memory. When memory is allocated successfully, it returns a pointer to that block, otherwise
it returns NULL. By dividing the necessary number of elements by each one's individual size,
the block's size is calculated. For example:

int* ptr = (int*) malloc(5 * sizeof(int)); // Allocates memory for 5 integers

2. calloc:

Resizing a previously allocated memory block is possible with the realloc (reallocate) function.
It accepts two arguments: the new size in bytes and a pointer to the current block. Upon
successful reallocation, a pointer to the newly allocated memory is returned. If not, NULL is
returned. Here's an example:

int* ptr = (int*) calloc(5, sizeof(int)); // Allocates memory for an array of 5

integers
3. realloc:

The realloc (reallocate) function allows you to resize a previously allocated memory block. It
takes a pointer to the existing block and the new size in bytes as arguments. If reallocation is
successful, it returns a pointer to the reallocated memory. Otherwise, it returns NULL. Example
usage:

int* ptr = (int*) malloc(5 * sizeof(int)); // Allocates memory for 5 integers

ptr = (int*) realloc(ptr, 10 * sizeof(int)); // Reallocates memory for 10 integers

The concept of dynamic memory allocation in c language enables the C programmer to

allocate memory at runtime. Dynamic memory allocation in c language is possible by 4
functions of stdlib.h header file.

1. malloc()
2. calloc()
3. realloc()
4. free()
Before learning above functions, let's understand the difference between static memory
allocation and dynamic memory allocation.

Static memory allocation Dynamic memory allocation

Memory is allocated at compile time. Memory is allocated at run time.

Memory can't be increased while executing Memory can be increased while executing
program. program.

Used in array. Used in linked list.

The methods used for dynamic memory allocation.

malloc() allocates single block of requested memory.

calloc() allocates multiple block of requested memory.

realloc() reallocates the memory occupied by malloc() or calloc() functions.

free() frees the dynamically allocated memory.

Linked List
A linked list is a fundamental data structure in computer science. It mainly allows efficient
insertion and deletion operations compared to arrays. Like arrays, it is also used to implement
other data structures like stack, queue and deque.

What is a Linked List?

A linked list is a linear data structure that consists of a series of nodes connected by pointers
(in C or C++) or references (in Java, Python and JavaScript). Each node contains data and a
pointer/reference to the next node in the list. Unlike arrays, linked lists allow for efficient
insertion or removal of elements from any position in the list, as the nodes are not stored
contiguously in memory.
Linked Lists vs Arrays
Linked List:
Data Structure: Non-contiguous
Memory Allocation: Typically allocated one by one to individual elements
Insertion/Deletion: Efficient
Access: Sequential
Array:
Data Structure: Contiguous
Memory Allocation: Typically allocated to the whole array
Insertion/Deletion: Inefficient
Access: Random

Linked List is a linear data structure, in which elements are not stored at a contiguous
location, rather they are linked using pointers. Linked List forms a series of connected
nodes, where each node stores the data and the address of the next node.

Node Structure: A node in a linked list typically consists of two components:

1. Data: It holds the actual value or data associated with the node.
2. Next Pointer or Reference: It stores the memory address (reference) of the next node
in the sequence.

Head and Tail: The linked list is accessed through the head node, which points to the first
node in the list. The last node in the list points to NULL or nullptr, indicating the end of the
list. This node is known as the tail node.

Advantages of Linked Lists (or Most Common Use Cases):

 1. Linked Lists are mostly used because of their effective insertion and deletion. We
only need to change few pointers (or references) to insert (or delete) an item in the
middle.
2. Insertion and deletion at any point in a linked list take O(1) time. Whereas in an array
data structure, insertion / deletion in the middle takes O(n) time.
3. This data structure is simple and can be also used to implement a stack, queues, and
other abstract data structures.
4. Implementation of Queue and Deque data structures: Simple array implementation is
not efficient at all. We must use circular array to efficiently implement which is
complex. But with linked list, it is easy and straightforward. That is why most of the
language libraries use Linked List internally to implement these data structures.
5. Linked List might turn out to be more space efficient compare to arrays in cases where
we cannot guess the number of elements in advance. In case of arrays, the whole
memory for items is allocated together. Even with dynamic sized arrays like vector in
C++ or list in Python or Array List in Java. the internal working involves de-allocation
of whole memory and allocation of a bigger chunk when insertions happen beyond
the current capacity.
Applications of Linked Lists:
1. Linked Lists can be used to implement stacks, queue, deque, sparse matrices and
adjacency list representation of graphs.
2. Dynamic memory allocation in operating systems and compilers (linked list of free
blocks).
3. Manipulation of polynomials
4. Arithmetic operations on long integers.
5. In operating systems, they can be used in Memory management, process scheduling
(for example circular linked list for round robin scheduling) and file system.
6. Algorithms that need to frequently insert or delete items from large collections of
data.
7. LRU cache, which uses a doubly linked list to keep track of the most recently used
items in a cache.
Applications of Linked Lists in real world:
1. The list of songs in the music player are linked to the previous and next songs.
2. In a web browser, previous and next web page URLs can be linked through the
previous and next buttons (Doubly Linked List)
3. In image viewer, the previous and next images can be linked with the help of the
previous and next buttons (Doubly Linked List)
4. Circular Linked Lists can be used to implement things in round manner where we go
to every element one by one.
5. Linked List are preferred over arrays for implementations of Queue and Deque data
structures because of fast deletions (or insertions) from the front of the linked lists.
Disadvantages of Linked Lists:
 1. Slow Access Time: Accessing elements in a linked list can be slow, as you need to
traverse the linked list to find the element you are looking for, which is an O(n)
operation. This makes linked lists a poor choice for situations where you need to
access elements quickly.
2. Pointers or References: Linked lists use pointers or references to access the next node,
which can make them more complex to understand and use compared to arrays. This
complexity can make linked lists more difficult to debug and maintain.
3. Higher overhead: Linked lists have a higher overhead compared to arrays, as each
node in a linked list requires extra memory to store the reference to the next node.
4. Cache Inefficiency: Linked lists are cache-inefficient because the memory is not
contiguous. This means that when you traverse a linked list, you are not likely to get
the data you need in the cache, leading to cache misses and slow performance.
5. Easy to use : Arrays are relatively very easy to use and are available as core of
programming languages
Types of Linked List
1. Singly Linked List
2. Doubly Linked List
3. Circular Linked List
4. Circular Doubly Linked List

Linked List Applications

1. Implementing stacks and queues using linked lists.
2. Using linked lists to handle collisions in hash tables.
3. Representing graphs using linked lists.
4. Allocating and deallocating memory dynamically.

Singly linked list

Singly linked list is a linear data structure in which the elements are not stored in contiguous
memory locations and each element is connected only to its next element using a pointer.

A singly linked list is a fundamental data structure in computer science and programming, it
consists of nodes where each node contains a data field and a reference to the next node in
the node. The last node points to null, indicating the end of the list. This linear structure
supports efficient insertion and deletion operations, making it widely used in various
applications. In this tutorial, we’ll explore the node structure, understand the operations on
singly linked lists (traversal, searching, length determination, insertion, and deletion), and
provide detailed explanations and code examples to implement these operations effectively.

What is Singly Linked List?

A singly linked list is a fundamental data structure in computer science and programming. It
is a collection of nodes where each node contains a data field and a reference (link) to the
next node in the sequence. The last node in the list points to null, indicating the end of the
list. This linear data structure allows for efficient insertion and deletion operations, making
it a popular choice for various applications.

Understanding Node Structure

In a singly linked list, each node consists of two parts: data and a pointer to the next node.
The data part stores the actual information, while the pointer (or reference) part stores the
address of the next node in the sequence. This structure allows nodes to be dynamically linked
together, forming a chain-like sequence.

In this representation, each box represents a node, with an arrow indicating the link to the
next node. The last node points to NULL, indicating the end of the list.

Node Structure of Singly Linked List

In most programming languages, a node in a singly linked list is typically defined using a
class or a struct.
Node Creation
struct node
{
int data;
struct node *next;
};
struct node *head, *ptr;
ptr = (struct node *)malloc(sizeof(struct node *));

Insertion

The insertion into a singly linked list can be performed at different positions. Based on the
position of the new node being inserted, the insertion is categorized into the following
categories.

SN Operation Description

1 Insertion at It involves inserting any element at the front of the list. We just need to
beginning a few link adjustments to make the new node as the head of the list.

2 Insertion at end It involves insertion at the last of the linked list. The new node can be
of the list inserted as the only node in the list or it can be inserted as the last one.
Different logics are implemented in each scenario.

3 Insertion after It involves insertion after the specified node of the linked list. We need
specified node to skip the desired number of nodes in order to reach the node after
which the new node will be inserted. .

Deletion and Traversing

The Deletion of a node from a singly linked list can be performed at different positions. Based
on the position of the node being deleted, the operation is categorized into the following
categories.

SN Operation Description

1 Deletion at It involves deletion of a node from the beginning of the list. This is the
beginning simplest operation among all. It just needs a few adjustments in the node
pointers.
 2 Deletion at the It involves deleting the last node of the list. The list can either be empty
end of the list or full. Different logic is implemented for the different scenarios.

3 Deletion after It involves deleting the node after the specified node in the list. we need
specified node to skip the desired number of nodes to reach the node after which the
node will be deleted. This requires traversing through the list.

4 Traversing In traversing, we simply visit each node of the list at least once in order
to perform some specific operation on it, for example, printing data part
of each node present in the list.

5 Searching In searching, we match each element of the list with the given element.
If the element is found on any of the location then location of that
element is returned otherwise null is returned. .

Double-linked list:

In a doubly linked list, each node contains references to both the next and previous nodes.
This allows for traversal in both forward and backward directions, but it requires additional
memory for the backward reference.

Circular linked list:

In a circular linked list, the last node points back to the head node, creating a circular
structure. It can be either singly or doubly linked.
Operations on Linked Lists

Insertion: Adding a new node to a linked list involves adjusting the pointers of the existing
nodes to maintain the proper sequence. Insertion can be performed at the beginning, end, or
any position within the list

Deletion: Removing a node from a linked list requires adjusting the pointers of the
neighbouring nodes to bridge the gap left by the deleted node. Deletion can be performed at
the beginning, end, or any position within the list.

Searching: Searching for a specific value in a linked list involves traversing the list from the
head node until the value is found or the end of the list is reached.