Summary of Pointer, Structure & Linked List
Goldius Leonard / CC01 / 2301857102 Data Structure
Summary of Pointer, Structure & Linked
List
Data
is one of the most important part of a system to make it run well. We have
known that one variable of data can store one data at a time. How about several
data with the same type? Therefore we need an array (a collection of items stored at contiguous memory locations
and elements can be accessed randomly using indices of an array) to store it. We have learnt that an
array should be created with a certain size and cannot be expanded nor minimized.
This may affect the memory usage of a program.
Dynamic Allocation (Malloc)
The solution
of keeping the memory usage as low as possible can be done with memory allocation
or malloc() syntax in C language. This syntax allocates memory for a
certain size. If we didn’t need it anymore, we can remove the allocated memory using
free() syntax. Here is the example of the usage of malloc() and free().
If you pay
attention to the “ptr” variable, you have learnt that it is a pointer.
Pointer
A pointer
is a variable whose value is the address of another variable,
i.e., direct address of the memory location. Pointer can be implemented
in any type of data. Two symbols that is used in pointer are &(address of) which
is used to call the address of a variable and *(asterisk) which is used to declare
pointer.
int *ip;
/* pointer to an integer */
double *dp; /* pointer to a double */
float *fp;
/* pointer to a float */
char *ch
/* pointer to a character */
A pointer
of pointer is a variable whose value is the address of
another pointer. Pointer of pointer is almost the as pointer, except the usage
of two(2) asterisks (**).
int **ip;
/* pointer of pointer to an integer */
double **dp; /* pointer of pointer to a double */
float **fp;
/* pointer of pointer to a float */
char **ch
/* pointer of pointer to a character */
Data
structure is an
arrangement of data, either in the computer’s memory or on the disk
storage. It is not only
about array, but there are many other types of data structure that we
know now, such as: Linked List, Tree (Binary Tree, AVL Tree, B-Tree,
Red-Black Tree, etc), Hash Table, Stack, Queue, and Graph. At this
time we will focus on Linked List data structure. Before we enter to
linked list, we need to recall our knowledge about struct (structure) in c.
Structure
Structure
is a user defined data type in C/C++. It means
we can create it as a group of certain data types into a single structure.
Below is the example to declare structure in c.
struct address
{
char name[50];
char street[100];
char city[50];
char state[20];
int pin;
};
We cannot
initialize a value to struct during the declaring structure, except using
curly braces ‘{}’.
struct Point
{
int x, y;
};
struct Point2
{
int x = 5;
// COMPILER ERROR: cannot
initialize members here
int y = 2;
// COMPILER ERROR: cannot
initialize members here
};
int main()
{
// A valid initialization. member x gets value 0 and y
// gets value 1. The order of declaration is followed.
struct
Point p1 = {0, 1};
}
After we know about structure, we will learn
the concept of linked list first. Linked List is a linear data structure, in which
the elements are not stored at contiguous memory locations. Linked
list can be analogized as a train with a locomotive and its railway wagon.
The locomotive is the head of a Linked List and the railway wagon is the
node of a Linked List. The last railway wagon will be the tail of a Linked
List.
The
advantage of Linked List are :
· Fast insertion and deletion any location
· Can accommodate any number of data (unpredictable number of
data)
The disadvantage of Linked List are :
· Slow on searching (linear from head)
· Used more memory to allocate the pointer
Every node in Linked List has a value and a pointer to
the next node (pointer that stores the address of the next node).
Linked
List has several types, such as :
· Single Linked List / Singly Linked List (every node consist of value and next
pointer)
· Double Linked List / Doubly Linked List (every node consist of value, next pointer and
previous pointer)
How to
declare Double Linked List :
struct tnode {
int value;
struct tnode
*next;
struct tnode
*prev;
};
struct tnode *head = 0;
struct tnode *tail = 0;
· Circular Single Linked List / Circular Singly Linked
List (every node consist of value and next
pointer, but the next pointer of tail is the head)
Characteristic of circular linked list
:
-
last node
contains a pointer to the first node
-
no storing of
NULL value
· Circular Double Linked List / Circular Doubly
Linked List (every node
consist of value, next pointer and previous pointer, but the next pointer of
tail is the head and the previous pointer of head is the tail)
Following
are the basic operations supported by a linked list.
·
Insertion − Adds an element at the beginning / middle / last of the list.
·
Deletion − Deletes an element at the beginning / middle / last of the
list.
·
Display − Displays the complete list.
·
Search − Searches an element using the given key.
Here are the algorithm for creating single
linked list.
struct tnode {
int value;
struct tnode *next;
};
struct tnode *head = 0;
Here are the algorithm for insertion at the
beginning of the single linked list.
•
First you need to
allocate a new node and assign value to it, connect it with the old head and change
the old head to the new head which is the new node.
struct tnode *node =
(struct
tnode*) malloc(sizeof(struct
tnode));
node->value = x;
node->next = head;
head = node;
Here are the algorithm for deletion of a certain
node in single linked list.
•
First you need to find the location of the node that you want
to delete using curr (current) and del (delete) pointer.
•
There are two conditions
we should pay attention to:
1.
if x is in a
head node
2.
if x is not in
a head node
struct tnode *curr = head;
// if x is in head node
if ( head->value == x ) {
head = head->next;
free(curr);
}
// 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);
}
Here are the algorithm for creating double
linked list.
struct tnode {
int value;
struct tnode *next;
struct tnode *prev;
};
struct tnode *head = 0;
struct tnode *tail = 0;
Here are the algorithm for insertion at the end
(behind the tail) of double linked list.
•
First you need to
allocate a new node and assign value to it, connect it with the existing list
and change the tail to the new node.
struct tnode *node =
(struct
tnode*) malloc(sizeof(struct
tnode));
node->value = x;
node->next = NULL;
node->prev = tail;
tail->next = node;
tail = node;
Here are the algorithm for insertion at the
middle of double linked list.
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;
Here are the algorithm for deletion of node in
double linked list.
•
If the node
to be deleted is the only node:
free(head);
head
= NULL;
tail
= NULL;
•
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;
•
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);
Other Reference (Beside Slide):
Komentar
Posting Komentar