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
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.
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 6x3 + 9x2 + 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
- If the node to be deleted is
head:
head = head->next;
free(head->prev);
head->prev = NULL;
- If the node to be deleted is tail:
tail = tail->prev;
free(tail->next);
tail->next = NULL;
Doubly
Linked List: Delete
- 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
