• Single Linked List
• Polynomial Representation
• Circular Single Linked List
• Double Linked List
• Circular Doubly Linked List
• Header Linked List
Single Linked List
use to create a list, we first need to define a node structure for the list.
Ex:
struct nodes{
int value;
struct nodes *next;
};
struct nodes *head = 0; //head = pointer to the first element in our linked list.
How 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.
Ex:
struct tnode *node =
(struct
tnode*) malloc(sizeof(struct tnode));
node->value = x;
node->next = head;
head = node;
Now How to delete a value that we add before?
first we should find the location
of node which store the value we want
to delete, remove it, and connect the remaining
linked list.
Ex:
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);
}Polynomial Representation
A polynomial is an expression that contains more than two terms. A term is made up of coefficient and exponent. An example of polynomial is P(x) = 4x^3+6x^2+7x+9
Detail:
Input:
1st number = 5x^2 + 4x^1 + 2x^0
2nd number = 5x^1 + 5x^0
Output:
5x^2 + 9x^1 + 7x^0
Input:
1st number = 5x^3 + 4x^2 + 2x^0
2nd number = 5x^1 + 5x^0
Output:
5x^3 + 4x^2 + 5x^1 + 7x^0
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
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.
Ex:
struct nodes {
int
value;
struct nodes *next;
struct nodes *prev;
};
•
struct nodes *head = 0;
struct nodes *tail = 0;
How to insert new value?
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.
Ex:
struct tnode *node =
(struct
tnode*) malloc(sizeof(struct tnode));
node->value = x;
node->next = NULL;
node->prev = tail;
tail->next = node;
tail = node;
Now How to delete the new value?
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:
Ex:
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);
Circular Double Linked List
It is similar with circular single
linked list, but total pointer
in each node here is 2 (two) pointers.
Header Linked List
aheader linked list is linked list that always contain a special note at the front of the list, this special
node is called headednote.
aheader linked list is linked list that always contain a special note at the front of the list, this special
node is called headednote.
1 .Grounded Header list is the header list where the last node contains the null pointer. Grounded comes from the fact that many text use the electrical ground symbol to indicate the null pointer.
- Location Of first node is written as:
PTR->LINK(HEAD)
Where as in singly linked list we write it as PTR->HEAD
- Condition to check empty header linked list:
2. Circular header list is a header list where the last more points back to the header node .the term node by itself normally refer to an ordinary node not the header node, when used with header list. Thus the first node in header is the node following the header node and the list.
- location of the first node is:
- Location Of first node is written as:
PTR->LINK(HEAD)- Condition to check empty Circular header linked list:
LINK(HEAD)=HEAD.
