pert ke 2 - Linked List Implementation I - 2101680123 - MILLIADY KUSNADI THE BU HIAP

Linked List Implementation I

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

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

C.   Single Linked List: Insert

Append a new node in front of head.

Assuming there is already a linked list

containing 10, 35, 27.

D.   Single Linked List: Insert

How about the algorithm of inserting new node in the middle and in the last of the single linked list?

Can you try it by yourself?

You should try!

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

Supposed the value we want to remove is x and

assuming x is exist in linked list and it is unique.

There are two conditions we should pay attention to:

if x is in a head node or x is not in a head node.

F.    Single Linked List: Delete

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);

}

G.  Polynomial Representation

•         Polynomial is given as 6x³ + 9x² + 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.

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

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

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

•      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);