Summary linked list

LINKED LIST
A linked list is a linear data structure, in which the elements are not
stored at contiguous memory locations. The elements in a linked list are
linked using pointers as shown in the below figure:




In simple words, a linked list consists of nodes where each node contains
a data field and a link(reference) to the next node in the list.
Like arrays, Linked List is a linear data structure. Unlike arrays, linked
list elements are not stored at a contiguous location.


1. CONCEPT OF LINKED LIST
1. Each node in a linked list consists of two parts: the data/value being
stored and a reference/link to the next node.
2. The last node in the list points to null to indicate the end of the list.
3. Unlike arrays, linked lists don't require consecutive memory
locations. Nodes can be scattered throughout memory.
4. This flexibility allows dynamic resizing and efficient insertion and
deletion operations at any position in the list.
5. Linked lists are useful when frequent modifications to the data
structure are expected, like inserting or removing elements.
6. However, accessing elements in a linked list sequentially is slower
compared to arrays because you need to follow the references from
node to node.
7. There are different types of linked lists: singly linked lists (with
references to the next node only), doubly linked lists (with references
to both the previous and next nodes), and circular linked lists (where
the last node points back to the first node).
8. Singly linked lists are the simplest form and require less memory per
node, while doubly linked lists allow for more efficient traversal in both
directions.
9. Circular linked lists are useful in scenarios where cyclic operations or
circular data representation are needed.
10. Overall, linked lists provide flexibility and efficiency for organizing
and managing data in a linear structure, especially when frequent
insertions, deletions, or dynamic resizing are required.
2. MEMORY REPRESENTATION

,1. Each node in a linked list is dynamically allocated its own memory
space.
2. A node contains two components: the data/value being stored and a
reference (or link) to the next node.
3. The memory for each node includes space for the data and the
reference.
4. Nodes are linked together by storing the memory address of the next
node in the current node's reference.
5. The last node in the list typically has a reference that points to null
to indicate the end of the list.
6. The memory allocation for nodes in a linked list is dynamic, allowing
for efficient resizing and modification.
7. Each node can have a different size in memory, depending on the size
of the data and the size of the reference.
8. The dynamic memory allocation allows for efficient insertion and
deletion operations in a linked list.
9. The memory representation of a linked list reflects the sequential
connection of nodes, forming the linear structure.
10. Overall, linked lists offer flexibility in memory allocation, enabling
efficient management of data in a dynamic structure.
3. SINGLE LINKED LIST
A singly linked list is a type of linked list where each node contains a
data element and a reference (link) to the next node in the sequence. In
a singly linked list, traversal is possible only in one direction, from the
head (the first node) to the tail (the last node).


Here are some key points about singly linked lists:


1. Node Structure: Each node in a singly linked list consists of two
components:
- Data: The value or payload stored in the node.
- Next: A reference (pointer) to the next node in the list.


2. Head and Tail: The head points to the first node, and the tail points
to the last node in the list. The tail node's next reference is typically set
to NULL to indicate the end of the list.


3. Traversal: To traverse a singly linked list, we start at the head and
follow the next references until we reach the tail. This allows sequential
access to the elements.

, 4. Insertion and Deletion: Inserting or deleting a node in a singly linked
list involves adjusting the next references of the affected nodes.
Insertion can be done at the beginning (prepend), at the end (append),
or at any position in the middle. Deletion involves updating the next
reference of the preceding node to bypass the deleted node.


5. Dynamic Size: Singly linked lists can grow and shrink dynamically as
nodes are added or removed. This makes them suitable for scenarios
where the size of the list may change frequently.


Singly linked lists are commonly used when efficient insertion and
deletion operations are required, but random access to elements is not
a primary concern. They are used in various applications, such as
implementing stacks, queues, and as building blocks for more complex
data structures.
4. TRAVERSAL
Traversing a singly linked list means visiting each node in the list to
access or perform some operation on its data.
Displaying the contents of a linked list is known as traversing a linked
list. It is very simple.
The algorithm for traversing a list
• Start with the head of the list. Access the content of the head
node if it is not null.
• Then go to the next node(if exists) and access the node
information
• Continue until no more nodes (that is, you have reached the null
node)
The following section of a code shows how to traverse a linked list.
struct node *ptr = head;
printf("\n\nList elements are - \n");
while(ptr != NULL)
{
printf("%d ",ptr->data);
ptr = ptr->next;
}
We keep moving the ptr node to the next one and display its contents.
When ptr is NULL, we know that we have reached the end of the linked
list so we get out of the while loop.