List

An array is a collection of elements of similar data type. This

collection is finite. And the elements are stored at adjacent memory
locations. Thus array has to be finite in nature i.e. the size of the array
should be specified.

For example: an array of 5 numbers-means the array size should not be less
than 5 as well as the elements are numbers (either all are integer values are
floating type values but not both)
Thus we can say array of n number of elements. Remember usually
array elements are starting from 0th location; hence n number of elements
can be counted from 0 to n-1. (No doubt, even we can store the elements
from any location) the range of array is between a[0] to a[n-1]. (Here a is
name of array). Range means total number of elements in the array. All these
elements are always stored at contiguous memory locations. Any element of
the array can be represented using index and name of the array. That means-
a[0] represents the value stored at 0th location of the array, a[2] represents
the value stored at 2nd location of the array and so on.

The syntax for array declaration is

Data type array_name[size_of_array];
For example: int a[6]
The array a of size 6, has all the elements which are of integer type.

a[6]

1
 Name index
Of the of
Array location

Let us understand such arrangement of array elements by following figure

a[0] a[1] a[2] a[3] a[4] a[5] a[6]

10 20 30 40 50 60 70

Types of arrays
The arrays can be categorized as
1. One dimensional arrays
2. Multidimensional arrays.
One dimensional array
They are called one-dimensional because the data can be viewed
entirely in one dimension. What that means is that you can think of the data
in the array as being essentially one long chain. As we will see in the next
topic, arrays can also extend to 2 dimensions, 3 dimensions, or any number
of dimensions that you choose. The effect that the dimensions have on
accessing the data is that one index number is needed for each dimension. In
a one-dimensional array we can think of the single index as being an
element's location in the list.

Example program for one dimensional array

/*searching a number*/

2
#include<stdio.h>
#include<conio.h>
void main()
{
int a[20],i,count,n,x,b;
clrscr();
printf("\n eneter the number of elements:");
scanf("%d",&n);
printf("\n enter the array elements:");
for(i=0;i<n;i++)/*accepting the values in the array using
for loop*/

{
scanf("%d",&a[i]);
}
printf("\n enter the element u want to search:");
scanf("%d",&x);
for(i=0;i<n;i++) /* searching the number using for loop*/
{
if(x==a[i])
{
count=1;
b=i;
}
}
if(count==1)
printf("match found and the element is stored in %d position:",b);

3
 else
printf("match not found:");
getch();
}

Output1
eneter the number of elements:3

enter the array elements:10

20
30
enter the element u want to search:10
match found and the element is stored in 0 position:
Output2
eneter the number of elements:3
enter the array elements:10
20
30
enter the element u want to search:40
match not found:

Two dimensional arrays

In two dimensional array the elements are stored in rows and columns.
Thus to denote rows and columns we required two indices for the array.
With the help of the indices we can decide at which position the element is
stored in the array. The following figure shows how elements can be stored
in two dimensional arrays

4
 Col0 Col1 Col2
10 20 30
Row0 (0,0) (0,1) (0,2)

40 50 60
(1,0) (1,1) (1,2)
Row1
Row2 70 80 90
(2,0) (2,1) (2,2)

The above array is a[3][3] i.e. of total size of row is 3 and total size of
columns is 3. if we want to access the element at position a[2][1] then that
will be = 80
The two dimensional array is also called matrix because they represent the
structure of matrix.
Example program for two dimensional array
/* addition of two matrices*/
#include<stdio.h>
#include<conio.h>
#include<math.h>
void main()
{
int a[20][20],b[20][20],c[20][20],i,j,n;
clrscr();
printf("enter the order of the matrix:");
scanf("%d",&n);
for(i=0;i<n;i++) /*getting the values of a matrix*/
for(j=0;j<n;j++)
{

5
printf("enter the element for a position %d%d :",i,j);
scanf("%d",&a[i][j]);
}
for(i=0;i<n;i++) /*getting the values of b matric*/
for(j=0;j<n;j++)
{
printf("\n enter the element for position %d%d :",i,j);
scanf("%d",&b[i][j]);
}
for(i=0;i<n;i++) /*adding a mtrix with b*/
for(j=0;j<n;j++)
{
c[i][j]=0;
c[i][j]=a[i][j]+b[i][j];
}
printf("\n the addition of two matrix a and b: is");
for(i=0;i<n;i++) /* printing the resultant matrix*/
{
printf("\n");
for(j=0;j<n;j++)
{
printf("\t%d",c[i][j]);
}
}
getch();
}

6
Output
enter the order of the matrix:2
enter the element for a matrix position 00 :1
enter the element for a matrix position 01 :1
enter the element for a matrix position 10 :1
enter the element for a matrix position 11 :1
enter the element for b matrix position 00 :1
enter the element for b matrix position 01 :1
enter the element for b matrix position 10 :1
enter the element for b matrix position 11 :1

the addition of two matrix a and b is:

2 2
2 2
Linked list:
Array is a static representation of list and linked list is a dynamic
representation of list. Here static means that in arrays the number of
elements is limited to the size of the array. If, total number of elements those
are to be stored in the array are very few then the space in the array gets
wasted. And dynamic means that as per memory requirement we can
allocate the space or we can de-allocate the memory.
In the array the elements are stored in the adjacent memory locations but this
is not the condition in the case of linked list. We can define linked list as a
collection of similar data items, which are stored in the nodes. Here is a
linked node.

Data Link
7
And these nodes form a linked list as follows.

10 20 30 40 Null

/*implementation of linked list*/

#include<stdio.h>
#include<conio.h>
typedef struct NODE
{
int data;
struct NODE *next;
}node;
node n1,n2,n3,n4;
node *one,*temp;
void main()
{
clrscr();
[Link]=10;
[Link]=&n2;
[Link]=20;
[Link]=&n3;
[Link]=30;
[Link]=&n4;
[Link]=40;
[Link]=NULL;
one=&n1;

8
temp=one;
while(temp!=NULL)
{
printf("\n%d",temp->data);
temp=temp->next;
}
getch();
}
output:
10
20
30
40
Advantages Of Linked List Over Arrays:
As we know the basic draw back of static memory and array is management
of memory. In both the cases either we create unnecessary extra memory or
we get lack of memory. For example if array size we have declared is 50 and
we have utilized only 10 locations then rest of the 40 locations get wasted or
even reverse can be the situation that means there may be a case that we
have to store 100 elements then we have to change the array size from 50 to
at least 100. Of course this is to be poor space utilization. So there is a
concept called dynamic memory management which came into picture for
proper utilization of memory.
In computer world the two words ‘static’ and ‘dynamic’ have great
importance. The static refers to an activity which is carried out at the time of
compilation of a program and before execution of the program whereas
dynamic means the activity carried out while the program is executed.

9
 The static memory management means allocating/deallocating of memory at
compilation time while the word refers to allocation/deallocation of memory
while program is running. The advantage of dynamic memory management
in handling the linked list is that we can create as many nodes as we desire
and if some nodes are not required we can deallocate them. Such a
dealliocated memory can be reallocated for some other nodes. Thus the
scheme results in 100% memory utilization.
Dynamic memory management in C:
In C language for allocating the memory dynamically ‘malloc’ function is
used we should include alloc.h file in our program to support ‘malloc’.
Similarly for deallocating the memory ‘free’ function is used.

Types of linked list:

There are various types of linked list such as
1. Singly linear linked list
2. Singly circular linked list
3. Doubly linear linked list
4. Doubly circular linked list
Singly linear linked list:

55 73 100 150 NULL

First or head
It is called singly because this list consists of only one link, to point to next
node or element. This is also called linear list because the last element points

10
to nothing it is linear in nature. The last field of last node is NULL which
means that there is no further list. The very first node is called head or first.
#include<stdlib.h>
#include<stdio.h>

struct Node{
int data;
struct Node *next;
};

void deleteStart(struct Node** head){

struct Node* temp = *head;

// If head is NULL it means Singly Linked List is empty

if(*head == NULL){
printf("Impossible to delete from empty Singly Linked List");
return;
}

// move head to next node

*head = (*head)->next;
printf("Deleted: %d\n", temp->data);
free(temp);
}

void insertStart(struct Node** head, int data){

11
 // dynamically create memory for this newNode
struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));

// assign data value

newNode->data = data;
// change the next node of this newNode
// to current head of Linked List
newNode->next = *head;

//re-assign head to this newNode

*head = newNode;
printf("Inserted %d\n",newNode->data);
}

void display(struct Node* node){

printf("\nLinked List: ");
// as linked list will end when Node is Null
while(node!=NULL){
printf("%d ",node->data);
node = node->next;
}
printf("\n");
}

int main()
{
struct Node* head = NULL;

12
 // Need '&' i.e. address as we need to change head
insertStart(&head,100);
insertStart(&head,80);
insertStart(&head,60);
insertStart(&head,40);
insertStart(&head,20);

// No Need for '&' as not changing head in display operation

display(head);

deleteStart(&head);
deleteStart(&head);
display(head);

return 0;
}
Singly circular linked list:
In this type of linked list only one link is used to point to next element and
this list is circular means that the last node’s link field points to be the first
or head node. That means according to example after 100 the next number
will be [Link] the list is circular in nature.

25 50 75 100

13
 Doubly linear linked list:

55 100 105 110

Null
Null

The list called doubly because each node has two pointers previous end
and next pointers. The previous pointer points to previous node and next
pointer points to next node. Only in the case of head node the previous
pointer is obviously NULL and last node’s next pointer points to NULL.
This list is a linear one.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

struct node {
int data;
int key;

struct node *next;

struct node *prev;
};

//this link always point to first Link

struct node *head = NULL;

14
//this link always point to last Link
struct node *last = NULL;

struct node *current = NULL;

//is list empty

bool isEmpty() {
return head == NULL;
}

int length() {
int length = 0;
struct node *current;

for(current = head; current != NULL; current = current->next){

length++;
}

return length;
}

//display the list in from first to last

void displayForward() {

//start from the beginning

struct node *ptr = head;

15
 //navigate till the end of the list
printf("\n[ ");

while(ptr != NULL) {
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}

printf(" ]");
}

//display the list from last to first

void displayBackward() {

//start from the last

struct node *ptr = last;

//navigate till the start of the list

printf("\n[ ");

while(ptr != NULL) {

//print data
printf("(%d,%d) ",ptr->key,ptr->data);

//move to next item

16
 ptr = ptr ->prev;

//insert link at the first location

void insertFirst(int key, int data) {

//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;

if(isEmpty()) {
//make it the last link
last = link;
} else {
//update first prev link
head->prev = link;
}

//point it to old first link

link->next = head;

//point first to new first link

head = link;

17
}

//insert link at the last location

void insertLast(int key, int data) {

//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;

if(isEmpty()) {
//make it the last link
last = link;
} else {
//make link a new last link
last->next = link;

//mark old last node as prev of new link

link->prev = last;
}

//point last to new last node

last = link;
}

//delete first item

struct node* deleteFirst() {

18
 //save reference to first link
struct node *tempLink = head;

//if only one link

if(head->next == NULL){
last = NULL;
} else {
head->next->prev = NULL;
}

head = head->next;
//return the deleted link
return tempLink;
}

//delete link at the last location

struct node* deleteLast() {

//save reference to last link
struct node *tempLink = last;

//if only one link

if(head->next == NULL) {
head = NULL;
} else {
last->prev->next = NULL;

19
 }

last = last->prev;

//return the deleted link

return tempLink;
}

//delete a link with given key

struct node* delete(int key) {

//start from the first link

struct node* current = head;
struct node* previous = NULL;

//if list is empty

if(head == NULL) {
return NULL;
}

//navigate through list

while(current->key != key) {
//if it is last node

if(current->next == NULL) {
return NULL;

20
 } else {
//store reference to current link
previous = current;

//move to next link

current = current->next;
}
}

//found a match, update the link

if(current == head) {
//change first to point to next link
head = head->next;
} else {
//bypass the current link
current->prev->next = current->next;
}

if(current == last) {
//change last to point to prev link
last = current->prev;
} else {
current->next->prev = current->prev;
}

return current;
}

21
bool insertAfter(int key, int newKey, int data) {
//start from the first link
struct node *current = head;

//if list is empty

if(head == NULL) {
return false;
}

//navigate through list

while(current->key != key) {

//if it is last node

if(current->next == NULL) {
return false;
} else {
//move to next link
current = current->next;
}
}

//create a link
struct node *newLink = (struct node*) malloc(sizeof(struct node));
newLink->key = newKey;
newLink->data = data;

22
 if(current == last) {
newLink->next = NULL;
last = newLink;
} else {
newLink->next = current->next;
current->next->prev = newLink;
}

newLink->prev = current;
current->next = newLink;
return true;
}

void main() {
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);

printf("\nList (First to Last): ");

displayForward();

printf("\n");
printf("\nList (Last to first): ");
displayBackward();

23
 printf("\nList , after deleting first record: ");
deleteFirst();
displayForward();

printf("\nList , after deleting last record: ");

deleteLast();
displayForward();

printf("\nList , insert after key(4) : ");

insertAfter(4,7, 13);
displayForward();

printf("\nList , after delete key(4) : ");

delete(4);
displayForward();
}

Doubly circular linked list:

50

10 20 30 40

In circular doubly linked list the previous pointer of first node and the next
pointer of last node is pointed to head node. Head node is a special node
which may have any dummy data or it may have some useful information

24
such as total number of nodes in the list which may be used to simplify the
algorithms carrying various operations on the list.

25