Concept of Linked List

- list refers to a set of items organized sequentially.

- An array is an example of a list. The sequential organization is provided

implicitly by its index.

- one major problem with arrays is that the size of an array must be
specified precisely at the beginning, that is, its size cannot be altered later.

- so a different way of representing a list is to make each item in the list part
of a structure that also contains a ‘link’ to the structure containing the next
item.

- This type of list is called a linked list because it is a list whose order is
given by links from one item to the next.

- Each structure of the list is called a node and consists of two fields, one
containing the item, and the other containing the address of the next item in
the list.

Definition of linked list:

A linked list is a collection of structures ordered not by their physical
placement in memory (like an array) but by logical links that are stored as
part of the data in the structure itself.

The link is in the form of a pointer to another structure of the same type.
Such a structure is represented as follows:

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

The first member is a data item and the second a pointer to the next node
in the list as shown below:

Definition: Structures that contain a member field that points to the same
structure type are called self-referential structures.

A node may represent the following general form :

The structure may contain more than one item with different data types.
However, one of the items must be a pointer of the type tag-name.
Example for two nodes:
struct link_list
{
int age;
struct link_list *next;
}

struct link_list node1, node2;

The above statement creates space for two nodes each containing two
empty fields as shown below:

The next pointer of node1 can be made to point node2 by the statement

node1. next = &node2;

The above statement stores the address of node2 into the field node1.
next and thus establishes a link between node1 and node2 as shown
below:

Note: ‘xxxx’ is the address of node2 where the value of the variable node2.
age will be stored.

Assigning values to the field age:

node1. age = 35;
node2. age = 49;

The result is as follows:

We may continue this process to create a linked list of any number of
values. For example,
node2. next = &node3;

would add another link provided node3 has been declared as a variable of
type struct link_list.

Every list must have an end. C has a special pointer value called null that
can be stored in the next field of the last node.

In our two-node list, the end of the list is marked as follows:

node2. next = 0;

The final linked list containing two nodes is shown below:

The value of the age member of node2 can be accessed using the next
member of node1 as follows:

printf( “%d\n” , node1. next->age) ;

Example program:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Node {
int intData;
char strData[50];
double doubleData;
struct Node* next;
};

struct Node* createNode(int intValue,

const char* stringValue, double

doubleValue) {

struct Node* newNode = (struct

Node*)malloc(sizeof(struct Node));

newNode->intData = intValue;

strcpy(newNode->strData,
stringValue);

newNode->doubleData = doubleValue;

newNode->next = NULL;

return newNode;

}
void printList(struct Node* head) {

struct Node* temp = head;

while (temp != NULL) {

printf("Integer: %d, String: %s,

Double: %.2f\n", temp->intData,

temp->strData, temp->doubleData);

temp = temp->next;

}
}

int main() {

struct Node* head = createNode(1, "Node1", 1.1);

struct Node* current = head;

current->next = createNode(2, "Node2", 2.2);

current = current->next;

current->next = createNode(3, "Node3", 3.3);

printList(head);

return 0;

}
Output:
Integer: 1, String: Node1, Double: 1.10
Integer: 2, String: Node2, Double: 2.20
Integer: 3, String: Node3, Double: 3.30

Example for accessing of far away nodes

#include <stdio.h>
#include <stdlib.h>

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

struct Node* createNode(int data) {

struct Node* newNode = (struct

Node*)malloc(sizeof(struct Node));

newNode->data = data;

newNode->next = NULL;

return newNode;
}

int main() {

struct Node* head = createNode(1);

struct Node* current = head;

 for (int i = 2; i <= 10; i++) {

current->next = createNode(i);

current = current->next;

// Accessing the 10th node's data

struct Node* node9 = head;

// Move to the 9th node

for (int i = 1; i < 9; i++) {

node9 = node9->next;
}

printf("Data in the 10th node:

%d\n", node9->next->data);

return 0;
}

Output:
Data in the 10th node: 10

Advantages of linked list

1. Linked list is a dynamic data structure. Hence, it can grow or shrink in
size during the execution of the program.

2. A linked list does not waste memory. It uses the memory that is just
needed for the list at any point of time.
3. The linked list provides flexibility in allowing the items to be rearranged
efficiently. It is easier to insert or delete items by rearranging the links

Limitations of linked list

1. Access to any arbitary item is a little cumbersome and time consuming.

2. Whenever we deal with fixed length list, it would be better to use an

array rather than a linked list.

3. Linked list uses more storage. This is because each item has an
additional link field.
Difference between linked list and arrays:

Feature Array Linked list

Memory Contiguous memory Non-contiguous
Allocation allocation. memory allocation
Access Direct access via Sequential access is
index required to reach an
element
Insertion and Inserting or deleting Insertion and
Deletion an element requires deletion are easier
shifting other since we only
elements. update the pointers
of the nodes.
Size Fixed size at the time Size is dynamic; we
of creation. can add or remove
To increase the size, nodes as needed
we must allocate a without worrying
larger array and copy about reallocating
the elements (costly memory.
operation).
Memory Requires less Requires extra
Usage memory overhead memory for storing
since there are no pointers in each
extra pointers. node
Cache Better cache Poorer cache
Performance performance due to performance
contiguous memory because nodes are
storage. scattered in
memory.
Applications Static datasets Dynamic datasets

Types of linked list

1. Linear list/Linear singly list:
A linear list is a data structure that has a start (first element) and end (last
element). Each item in the list points to the next item in a sequential
manner, forming a continuous sequence from start to end.

2. Circular list/Circular linked list

The circular linked lists have no beginning and no end. The last item points
back to the first item.

3. Two-way Or doubly linked list

The doubly linked list uses double set of pointers, one pointing to the next
item and the other pointing to the preceding item. This allows us to traverse
the list in either direction.

4. Two-way circular list/ Circular doubly linked list

Circular doubly linked lists employs both forward pointer and backward
pointer in circular form.
Basic list operations
1. Creating a list
2. Traversing the list
3. Counting the items in the list
4. Printing the list
5. Looking up an item for editing or printing
6. Inserting an item
7.Deleting an item
8. Concatenating two lists

Application of linked list

Linked list can be used to model many abstract data types. Some of them
are as follows:

1. Queue : If we restrict the process of insertions to one end of the list and
deletions to the other end, then we have a model of a queue. That is, we
can insert an item at the rear and remove an item at the front. This obeys
the discipline of “ first in, first out” (FIFO)

2. Stack : If we restrict insertions and deletions to occur only at one end of

the list, the beginning, then we model another data structure known as
stack. Stacks are also referred to as push-down lists. They are also
referred to as “ last in, first out” (LIFO) structures.

3. Trees : Lists, queues, stacks are all inherently one-dimensional. A tree

represents a two-dimensional linked list. Insertions and deletions can occur
at any level, depending on the specific tree structure and the rules
governing it. Example of trees could be an organizational chart or a family
tree.