Linked List Implementation 1
I. Single Linked List
To create a list, we first need to
define a node structure for the list.
Supposed we want to create a list
of integers.
struct tnode {
int
value;
struct
tnode *next;
};
struct tnode *head = 0;
II. Single Linked List : Insert
To insert a new value, first we
should dynamically allocate a new node and assign the value to it
and then
connect it with the existing linked list.
Supposed we want to append the new
node in
front of the head.
struct tnode *node =
(struct
tnode*) malloc(sizeof(struct tnode));
node->value = x;
node->next = head;
head
= node;
III. Single Linked List : Delete
To delete a value, first we should
find the location of node which store the value we want
to
delete, remove it, and connect the remaining linked
list.
struct
tnode *curr = head;
// if x is in head node
if
( head->value == x ) {
head = head->next;
free(curr);
}
}
// if x is in tail node
else
if(tail->value == x){
while(curr->next!=tail) curr
= curr->next;
free(tail); tail = curr;
tail->next
= NULL;
}
// if x is not in head node, find the
location
else
{
while ( curr->next->value != x ) curr =
curr->next;
struct tnode *del = curr->next;
curr->next = del->next;
free(del);
}
III. Polynomial Representation
•Polynomial is given as 6x3 + 9x2 + 1
•Every individual term in a
polynomial consists of two parts, a coefficient and a power
•Here, 6, 9, 7, and 1 are the
coefficients of the terms that have 3, 2, 1, and 0 as their
power respectively.
•Every term of a polynomial can be
represented as a node of the linked list.
\
IV. Circular Single Linked List
In circular, last node contains a
pointer to the first node. We can have a circular singly
linked list
as well as a circular doubly linked list. There is no storing of NULL values
in the list.
V. Doubly Linked List
Doubly
linked list or
two-way linked list is a linked list data structure with two link,
one that
contain reference to the next data and one that contain reference to
the
previous data.
struct tnode {
int
value;
struct
tnode *next;
struct
tnode *prev;
};
struct tnode *head = 0;
struct tnode *tail = 0;
VI. Doubly Linked List : Insert
Just like in a single linked list,
first we should allocate the new node and assign the value
to it, and then we connect the node with the existing
linked list.
Supposed we want to append the new
node behind
the tail.
struct tnode *node =
(struct
tnode*) malloc(sizeof(struct tnode));
node->value = x;
node->next = NULL;
node->prev = tail;
tail->next = node;
tail
= node;
VII. Doubly Linked List : Delete
There are 4 conditions we should
pay attention when deleting:
•The node to be deleted is the only
node in linked list.
•The node to be deleted is head.
•The node to be deleted is tail.
•The node to be deleted is not head
or tail.
1.
If the node to be deleted is the only node:
free(head);
head = NULL;
tail = NULL;
2.If
the node to be deleted is head:
head
= head->next;
free(head->prev);
head->prev = NULL;
3.If
the node to be deleted is tail:
tail
= tail->prev;
free(tail->next);
tail->next
= NULL;
4.If the node to be deleted is not in
head or tail:
struct tnode *curr = head;
while
( curr->next->value != x ) curr = curr->next;
struct
tnode *a = curr;
struct
tnode *del = curr->next;
struct
tnode *b = curr->next->next;
a->next
= b;
b->prev
= a;
free(del);
VIII. Circular Doubly Linked List
It is similar with circular single
linked list, but total pointer in each node here is
2
(two) pointers.
IX. Header Linked List
A header linked list is a special
type of linked list which contains a header node at
the beginning of the list. So, in a header linked list, START
(L) will not point to the first
node of the list but START (L) will contain the
address of the header node.
