Materi Pertemuan 3 COMP6048 – Data
Structure
Linked List Implementation I
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;
Notes :
“head” adalah pointer
menuju ke elemen pertama pada linked list.
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;
Notes:
Operator -> has the
same meaning as:
(*node).value = x;
(*node).next = head;
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.
Contoh:
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
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
thanks for the information from (https://www.geeksforgeeks.org/adding-two-polynomials-using-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.
11. 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;
22. 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;
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;
44. 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
Komentar
Posting Komentar