linkedlist

 

Linked Lists: An Overview

Definition:

A linked list is a linear data structure consisting of a sequence of elements called nodes. Each node contains data and a reference (or pointer) to the next node in the sequence.

Properties:

• Dynamic Size: Linked lists can grow or shrink in size dynamically as elements are added or removed.
• Flexibility: They allow for efficient insertion and deletion operations at any position in the list.
• Non-Contiguous Memory Allocation: Unlike arrays, linked list nodes can be scattered in memory, connected only by pointers.

Types of Linked Lists:

Singly Linked List:

In a singly linked list, each node contains data and a pointer to the next node in the sequence.

Doubly Linked List:

In a doubly linked list, each node contains data and pointers to both the next and previous nodes, allowing bidirectional traversal.

Circular Linked List:

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

Advantages of Linked Lists:

• Dynamic Size: Linked lists can expand or contract in size as needed, making them suitable for situations where the size is unpredictable.
• Efficient Insertion and Deletion: Insertion and deletion operations can be performed efficiently, especially when compared to arrays, which may require shifting elements.
• Flexible Memory Allocation: Linked lists use dynamic memory allocation, allowing for efficient use of memory.

Disadvantages of Linked Lists:

• No Random Access: Unlike arrays, linked lists do not support random access. Traversal is required to access elements at specific positions.
• Extra Memory Overhead: Linked lists require additional memory for storing pointers, which can increase memory usage compared to arrays.
• Traversal Overhead: Traversal through the list can be slower compared to arrays, especially for large lists

Representation of Linked List

Let's see how each node of the linked list is represented. Each node consists:

• A data item
• An address of another node

We wrap both the data item and the next node reference in a struct as:

struct node
{
  int data;
  struct node *next;
};

Understanding the structure of a linked list node is the key to having a grasp on it.

Each struct node has a data item and a pointer to another struct node. Let us create a simple Linked List with three items to understand how this works.

/* Initialize nodes */
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;

/* Allocate memory */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));

/* Assign data values */
one->data = 1;
two->data = 2;
three->data=3;

/* Connect nodes */
one->next = two;
two->next = three;
three->next = NULL;

/* Save address of first node in head */
head = one;

In just a few steps, we have created a simple linked list with three nodes.

Complexity of Linked Lists:

1. Time Complexity:

   • Access: O(n) - Linked lists do not support random access, so accessing an element requires traversing the list from the head.
   • Insertion/Deletion: O(1) - Insertion and deletion at the beginning of the list can be done in constant time by updating pointers.
   • Insertion/Deletion at End: O(n) - If we need to insert or delete at the end, we need to traverse the list to find the last node, resulting in linear time complexity.

2. Space Complexity:

   • O(n) - Linked lists require space proportional to the number of elements stored in the list.

Applications of Linked Lists:

1. Dynamic Memory Allocation: Linked lists are used in dynamic memory allocation systems like malloc/free in C, where memory blocks can be allocated and deallocated efficiently.

2. Implementation of Stacks and Queues: Linked lists are the basis for implementing stack and queue data structures. In a stack, elements are inserted and removed from one end (LIFO - Last In, First Out), while in a queue, elements are inserted at one end and removed from the other end (FIFO - First In, First Out).

3. File Systems: Linked lists are used in file systems to represent the structure of directories and files. Each node in the linked list represents a file or directory, and the pointers represent the hierarchical relationships.

4. Polynomial Representation: Linked lists are used to represent polynomial expressions, where each term is stored as a node with coefficients and exponents.

5. Graph Algorithms: Linked lists are used to represent adjacency lists in graph data structures, where each vertex has a linked list of adjacent vertices.

6. Polynomial Representation using Linked List

   In a polynomial, each term consists of a coefficient and an exponent. We can represent a polynomial using a linked list where each node contains the coefficient and exponent of a term.

   Node Structure:

   struct Node {
       int coefficient;
       int exponent;
       struct Node* next;
   };
   

   In this structure, coefficient represents the coefficient of the term, exponent represents the exponent, and next points to the next term in the polynomial.

   Addition of Single Variable Polynomials

   To add two single-variable polynomials, we traverse both linked lists simultaneously. At each step, we compare the exponents of the current terms:

   • If the exponents are equal, we add the coefficients and create a new term with the sum.
   • If the exponent of one polynomial is greater, we add the term to the result polynomial and move to the next term in that polynomial.
   • If the exponent of the other polynomial is greater, we add the term to the result polynomial and move to the next term in that polynomial.

   Subtraction of Single Variable Polynomials

   Subtraction of polynomials follows a similar approach to addition, except we subtract coefficients when the exponents match.

   Multiplication of Single Variable Polynomials

   For multiplication, we use the distributive property to multiply each term of one polynomial with every term of the other polynomial. Then, we add the resulting terms together.

   Addition, Subtraction, and Multiplication of Two-Variable Polynomials

   The operations for two-variable polynomials are similar to single-variable polynomials, but each term contains two exponents—one for each variable. The addition, subtraction, and multiplication operations follow the same principles but involve comparing and manipulating terms with two exponents.

   Example:

   Let's say we have two single-variable polynomials:

   • Polynomial A: $3{�}^2+2�+5$
   • Polynomial B: $2{�}^3-4�+1$

   We represent these polynomials using linked lists and perform addition, subtraction, and multiplication operations to obtain the results.