Session 2-Linked List Implementation-2101727190-Fedrick

Linked list divided to 6 subtopic:
• 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

Double 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.

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.

 Linked List devide into 2 types:

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.