2-Chandra Delon-2101662013

2-Chandra Delon-2101662013

Linked List:

-        Single Linked List

-        Polynomial Representation

-        Circular Single Linked List

-        Doubly Linked List

-        Circular Doubly Linked List

-        Header Linked List

Single Linked List
untuk membuat sebuah list , kita pertama-tama harus mendefinisikan sebuah struktur node untuk listnya. 
Bila kita mau membuat sebuah list type integer

struct tnode {

               int value;

               struct tnode *next;

};

struct tnode *head = 0;

Single Linked List: Insert

Untuk insert value yang baru, kita harus dynamically allocate a new node dan memasukan valuenya kedalam dan menghubungkannya dengan linked list yang tersedia.

Bila kita mau menambahkan node baru ke dalam head.

struct tnode *node =

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

node->value = x;

node->next  = head;

head = node;

Untuk menghapus sebuah value, kita harus mencari lokasi dari node dimana value yang ingit kita delete tersimpan, lalu di delete, kemudian sambungkan ke sisa linked list.

Bila value yang kita mau delete adalah x dan misalkan x itu berada didalam linked list dan kondisinya unik.
Ada 2 kondisi yang kita harus perhatikan:
Jika x di dalam head node atau tidak ada didalam head node.

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

}

Single Linked List: Delete

Deleting 31 (located at head)

Single Linked List: Delete

Deleting 35 (not located at head)

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.

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

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;

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;

Doubly Linked List: Insert

Supposed we want to insert a new node in a certain position (any

location between head and tail)

struct tnode *a = ??;

struct tnode *b = ??;

// the new node will be inserted between a and b

struct tnode *node =

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

node->value      = x;

node->next        = b;

node->prev        = a;

a->next = node;

b->prev               = node;

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;

Doubly Linked List: Delete

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;

Doubly Linked List: Delete

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

Circular Doubly Linked List

It is similar with circular single linked list, but total

pointer in each node here is 2 (two) pointers.

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.

Summary

               Linked list is a data structure that consists of a sequence of data records such that each record there is a field that contains a reference to the next record in the sequence