Linked List

A linked list can be perceived as a train or a sequence of nodes in which
each node contains one or more data fields and a pointer to the next node.
Every node in a linked list contains two parts, an integer and a pointer to
the next node. The left part of the node contains data
The right part of the node contains a pointer to the next node (or address
of the next node in sequence). The last node will have no next node
connected to it, so it will store a special value called NULL.
Difference between array and linked list:
A linked list does not store its elements in consecutive

memory locations and the user can add any number
of elements to it.
A linked list does not allow random access of data.
Elements in a linked list can be accessed only in a
sequential manner.
Similarities in array and linked list:
Both arrays and linked lists are a linear collection of data elements.
Like an array, insertions and deletions can be done at any point in the list
in a constant time
In C, we can implement a linked list using the following code:
struct node
{
int data;
struct node *next;
};
Singly linked list:
A singly linked list is the simplest type of linked list in which every node
contains some data and a pointer to the next node of the same data type.
A singly linked list allows traversal of data only in one way.
Algorithm for traversing a linked list:
Step 1: [INITIALIZE] SET PTR = START

Step 2: Repeat Steps 3 and 4 while PTR != NULL
Step 3: Apply Process to PTR DATA
Step 4: SET PTR = PTR NEXT
[END OF LOOP]
Step 5: EXIT
In this algorithm, we first initialize PTR with the address of START. So
now, PTR points to the first node of the linked list.
Then in Step 2, a while loop is executed which is repeated till PTR
processes the last node, that is until it encounters NULL.
In Step 3, we apply the process (e.g., print) to the current node, that is,
the node pointed by PTR.
In Step 4, we move to the next node by making the PTR variable point to
the node whose address is stored in the NEXT field
Algorithm to search a linked list

Step 1: [INITIALIZE] SET PTR = START
Step 2: Repeat Step 3 while PTR != NULL
Step 3: IF VAL = PTR DATA
SET POS = PTR
Go To Step 5
ELSE
SET PTR = PTR NEXT
[END OF IF]
[END OF LOOP]
Step 4: SET POS = NULL
Step 5: EXIT
In Step 1, we initialize the pointer variable PTR with START that
contains the address of the first node.
In Step 2, a while loop is executed which will compare every
node’s DATA with VAL for which the search is being made. If the
search is successful, that is, VAL has been found, then the address
of that node is stored in POS and the control jumps to the last
statement of the algorithm. However, if the search is
unsuccessful, POS is set to NULL which indicates that VAL is not
present in the linked list.
Algorithm to insert a new node at the beginning:
Step 1: IF AVAIL = NULL

Write OVERFLOW
Go to Step 7
[END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL NEXT
Step 4: SET DATA = VAL
Step 5: SET NEW_NODE NEXT = START
Step 6: SET START = NEW_NODE
Step 7: EXIT
In Step 1, we first check whether memory is available for the

new node. If the free memory has exhausted, then an OVERFLOW
message is printed. Otherwise, if a free memory cell is available,
then we allocate space for the new node. Set its DATA part with
the given VAL and the next part is initialized with the address of
the first node of the list, which is stored in START. Now, since
the new node is added as the first node of the list, it will now be
known as the START node, that is, the START pointer variable will
now hold the address of the NEW_NODE.
Algorithm to insert a new node at the end

Write OVERFLOW
Go to Step 1
[END OF IF]
Step 2: SET = AVAIL
Step 5: SET NEW_NODE = NULL
Step 6: SET PTR = START
Step 7: Repeat Step 8 while PTR NEXT != NULL
[END OF LOOP]
Step 9: SET PTR NEXT = NEW_NODE
Step 10: EXIT
Inserting a Node After a Given Node in a Linked List

OVERFLOW
Go to Step 12
[END OF IF]
Step 2: SET = AVAIL
Step 5: SET PTR = START
Step 6: SET PREPTR = PTR
Step 7: Repeat Steps 8 and 9 while PREPTR - > DATA!= NUM
Step 8: SET PREPTR = PTR
[END OF LOOP]
Step 10 : PREPTR NEXT = NEW_NODE
Step 11: SET NEW_NODE NEXT = PTR
Step 12: EXIT
Inserting a Node Before a Given Node in a Linked List
Deleting the First Node from a Linked List
Deleting the Last Node from a Linked List
Deleting the Node After a Given Node in a Linked List
CIRCULAR LINKED LISTs :
In a circular linked list, the last node contains a pointer to the

first node of the list. While traversing a circular linked list, we
can begin at any node and traverse the list in any direction,
forward or backward, until we reach the same node where we
started. Thus, a circular linked list has no beginning and no
ending. Circular linked lists are widely used in operating systems
for task maintenance. We can traverse the list until we find the
NEXT entry that contains the address of the first node of the list.
This denotes the end of the linked list.
Inserting a Node at the Beginning of a Circular Linked List

Inserting a Node at the End of a Circular Linked List
Deleting the First Node from a Circular Linked List
Deleting the Last Node from a Circular Linked List
DOUBLY LINKED LISTS :
A doubly linked list or a two-way linked list is a more complex

type of linked list which contains a pointer to the next as well as
the previous node in the sequence. Therefore, it consists of three
parts-data, a pointer to the next node, and a pointer to the
previous node
In C, the structure of a doubly linked list can be given as,
struct node
{
struct node *prev;
int data;
struct node *next;
};
The PREV field is used to store the address of the preceding node, which
enables us to traverse the list in the backward direction. A doubly linked
list provides the ease to manipulate the elements of the list as it maintains
pointers to nodes in both the directions. The main advantage of using a
doubly linked list is that it makes searching twice as efficient
Inserting a Node at the Beginning of a Doubly Linked List

Inserting a Node at the End of a Doubly Linked List
Inserting a Node After a Given Node in a Doubly Linked List
Inserting a Node Before a Given Node in a Doubly Linked
List
Deleting the First Node from a Doubly Linked List
Deleting the Last Node from a Doubly Linked List
Deleting the Node After a Given Node in a Doubly Linked
List
Deleting the Node Before a Given Node in a Doubly Linked
List

Linked List

Uploaded by

Copyright:

Available Formats

Linked List

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Linked List

Uploaded by

Copyright:

Available Formats

A linked list can be perceived as a train or a sequence of nodes in which

Difference between array and linked list:

A linked list does not store its elements in consecutive

Similarities in array and linked list:

In C, we can implement a linked list using the following code:

Step 1: [INITIALIZE] SET PTR = START

Algorithm to search a linked list

Algorithm to insert a new node at the beginning:

Step 1: IF AVAIL = NULL

In Step 1, we first check whether memory is available for the

Step 1: IF AVAIL = NULL

Inserting a Node After a Given Node in a Linked List

Step 1: IF AVAIL = NULL

CIRCULAR LINKED LISTs :

In a circular linked list, the last node contains a pointer to the

Inserting a Node at the Beginning of a Circular Linked List

DOUBLY LINKED LISTS :

A doubly linked list or a two-way linked list is a more complex

Inserting a Node at the Beginning of a Doubly Linked List

You might also like