2 - Linked List Implementation I - 2101702130 - Andrean

Pertemuan ke - 2
27-02-2018

Linked List:

- Single Linked List

Simplest linked list. 

Define a node structure :

struct tnode {

  int value;

  struct tnode *next;

}*head=NULL,*tail=NULL,*curr;

head is the pointer for the first element in our linked list.

tail is the pointer for the last element in our linked list.

Insert

Head:

struct tnode *node = (struct tnode*) malloc(sizeof(struct tnode)); //make a new node

node->value = x;

node->next  = head;

head = node;

Tail:

struct tnode *node = (struct tnode*) malloc(sizeof(struct tnode)); //make a new node

node->value = x;

node->next  = NULL;

tail->next = node;

tail = node;

Delete

// 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 has mainly two fields. exponent and coefficient. 

In each node the exponent field will store the corresponding exponent and the coefficient field will store the corresponding coefficient. Link field points to the next item in the polynomial.

- Circular Single Linked List

Last node point to first node(head) not point to NULL.

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

Define a node structure :

struct tnode {

  int value;

  struct tnode *next;

  struct tnode *prev;

}*head=NULL,*tail=NULL,*curr,*del;

Insert

Head:

struct tnode *node =(struct tnode*) malloc(sizeof(struct tnode));

node->value = x;

node->next  = head;

node->prev  = NULL;

head=node;

Tail:

struct tnode *node = (struct tnode*) malloc(sizeof(struct tnode));

node->value = x;

node->next  = NULL;

node->prev  = tail;

tail->next  = node;

tail = node;

Mid:

struct tnode *node =(struct tnode*) malloc(sizeof(struct tnode));

node->value  = x;

node->next  = b;

node->prev  = a;

a->next  = node;

b->prev  = node;

Delete

1. Deleted is the only node:

free(head);

head = NULL;

tail = NULL;

2. Deleted is head:
head = head->next;
free(head->prev);
head->prev = NULL;

3. Deleted is tail:
tail = tail->prev;
free(tail->next);
tail->next = NULL;

4. Deleted is not in head or tail:

  curr = head;

  while ( curr->next->value != x ) curr = curr->next;

  a   = curr;

  del = curr->next;

  b   = curr->next->next;

  a->next = b;

  b->prev = a;

  free(del);

- Circular Doubly Linked List

First node prev point to last node next.

Last node next point to first node prev.

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

2101702130 - Andrean