1 of 82

Data Structures�CS 19.203

By,

Dr. Mrinal Paliwal

2 of 82

Unit 2

Definition, single and multidimensional arrays, representation of arrays: row major order, and column major order, application of arrays, sparse matrices and

their representations. Singly linked lists, doubly linked list, circular linked list, insertion, deletion, traversal, polynomial representation and addition, generalized linked list.

3 of 82

Array & Linked list

ARRAYS

​

  • An array is defined as a set of finite number of homogeneous elements or same data items.
  • It means an array can contain one type of data only, either all integer, all float-point number or all character.
  • An array is defined as it is a collection of items stored at contiguous (adjoining ) memory locations. 

​

  • Items that are the same data type get stored together so that the position of each element can be calculated or retrieved easily.
  • Arrays can be fixed or flexible in length.

4 of 82

Array & Linked list

ARRAYS

5 of 82

Array & Linked list

  1. Single (ONE) Dimension Array
      • Array with one subscript

​

  • Two Dimension Array
    • Array with two subscripts (Rows and Column)

​

  • Multi Dimension Array
    • Array with Multiple subscripts

​

​

ARRAYS TYPES

6 of 82

Array & Linked list

ONE DIMENSIONAL ARRAY

7 of 82

Array & Linked list

TWO DIMENSIONAL ARRAY

8 of 82

Array & Linked list

An array with only one row or column is called one-dimensional array.

It is finite collection of n number of elements of same type such that:

    • can be referred by indexing.
    • The syntax Elements are stored in continuous locations.
    • Elements x to define one-dimensional array is:

Syntax: Datatype Array_Name [Size];

Where,

  • Datatype : Type of value it can store (Example: int, char, float)
  • Array_Name: To identify the array.
  • Size : The maximum number of elements that the array can hold.

ONE DIMENSIONAL ARRAY

9 of 82

Array & Linked list

ONE DIMENSIONAL ARRAY

To find the address of an element in an array the following formula is used-

​

Address of A[I] = B + W * (I – LB)

​

I = Subset of element whose address to be found, �B = Base address, �W = Storage size of one element store in any array(in byte), �LB = Lower Limit/Lower Bound of subscript

(If not specified assume zero).

10 of 82

Array & Linked list

Example: Given the base address of an array 

A[1300…………1900] as 1020 and the size of each element

is 2 bytes in the memory, find the address of A[1700]?  

Solution:

Given:�Base address B = 1020�Lower Limit/Lower Bound of subscript LB = 1300�Storage size of one element store in any array W = 2 Byte�Subset of element whose address to be found I = 1700

Formula:�Address of A[I] = B + W * (I – LB)

Solution:�Address of A[1700] = 1020 + 2 * (1700 – 1300)�                              = 1020 + 2 * (400)�                              = 1020 + 800�Address of A[1700] = 1820

11 of 82

Array & Linked list

Example: Given the base address of an array 

A[1300…………1900] as 1020 and the size of each element

is 2 bytes in the memory, find the address of A[1700]?  

Solution:

Given:�Base address B = 1020�Lower Limit/Lower Bound of subscript LB = 1300�Storage size of one element store in any array W = 2 Byte�Subset of element whose address to be found I = 1700

Formula:�Address of A[I] = B + W * (I – LB)

Solution:�Address of A[1700] = 1020 + 2 * (1700 – 1300)�                              = 1020 + 2 * (400)�                              = 1020 + 800�Address of A[1700] = 1820

12 of 82

Array & Linked list

13 of 82

BASIC OPERATIONS OF ARRAYS

  • Traverse Operation- In traversing operation of an array, each element of an array is accessed exactly for once for processing. This is also called visiting of an array.

​

  • Insertion Operation- Insert operation is to insert one or more data elements into an array. Based on the requirement, new element can be added at the beginning, end or any given index of array.

​

  • Deletion Operation- Deletion refers to removing an existing element from the array and re-organizing all elements of an array.

​

  • Search Operation- You can perform a search for array element based on its value or its index.

​

  • Update Operation- Update operation refers to updating an existing element from the array at a given index.

14 of 82

TRAVERSING IN ARRAYS

Traversing: It is used to access each data item exactly once so that it can be processed.

E.g. We have linear array A as below:

Here we will start from beginning and will go till last element and during this process we will access value of each element exactly once as below:

A [1] = 10 A [2] = 20 A [3] = 30

A [4] = 40 A [5] = 50

15 of 82

INSERTION IN ARRAYS

  1. Insertion at the end of array

Algorithm:

  1. If UB=MAX then write array is OVERFLOW & STOP
  2. READ DATA
  3. UB=UB+1

A[UB]=DATA

4. STOP

16 of 82

INSERTION IN ARRAYS

II. Insertion at the beginning of array

Algorithm:

  1. If UB=MAX then write array is OVERFLOW & STOP
  2. READ DATA
  3. K=UB
  4. Repeat Step(5) while K>=LB
  5. A[K+1]=A[K]

K=K-1

  1. A[LB]=DATA
  2. STOP

17 of 82

INSERTION IN ARRAYS

III. Insertion at a given location of array

Algorithm:

  1. If UB=MAX then write array is OVERFLOW & STOP
  2. READ DATA
  3. READ LOC
  4. K=UB
  5. Repeat Step(6) while K>=LOC
  6. A[K+1]=A[K]

K=K-1

  1. A[LOC]=DATA
  2. STOP

18 of 82

INSERTION IN ARRAYS

IV. Insertion in the sorted list of array

Algorithm:

  1. If UB=MAX then write array is OVERFLOW & STOP
  2. READ DATA
  3. K=LB
  4. Repeat Step(5) while A[K]<DATA
  5. K=K+1
  6. LOC=K

K=UB

7. Repeat Step(8) while K>=LOC

8. A[K+1]=A[K]

K=K-1

9. A[LOC]=DATA

10. STOP

19 of 82

INSERTION IN ARRAYS

  1. Deletion from the End

Algorithm:

  1. If N=0 then write array is UNDERFLOW & STOP
  2. A[UB]=Null
  3. UB=UB-1
  4. STOP

20 of 82

INSERTION IN ARRAYS

II. Deletion from the beginning

Algorithm:

  1. If N=0 then write array is UNDERFLOW & STOP
  2. K=LB
  3. Repeat Step(4) while K<UB
  4. A[K]=A[K+1]

K=K+1

  1. A[UB]=Null
  2. UB=UB-1
  3. STOP

21 of 82

INSERTION IN ARRAYS

III. Deletion of a given element

Algorithm:

  1. If N=0 then write array is UNDERFLOW & STOP
  2. Read DATA
  3. Read LOC
  4. K=LB
  5. Repeat Step(6) while A[K]!=DATA
  6. K=K+1
  7. Repeat Step(8) while K<UB
  8. A[K]=A[K+1]

K=K+1

  1. A[UB]=Null
  2. UB=UB-1
  3. STOP

22 of 82

LIMITATIONS IN ARRAYS

  • An array which is formed will be homogeneous. Thus, no array can have values of two data types.

​

  • While declaring an array, passing size of an array is compulsory, and the size must be a constant. Thus, there is either shortage or wastage of memory.

​

  • Shifting is required for insertion or deletion of elements in an array.
  • Data that is entered with the subscript, exceeds the array size and will be placed outside the array. Generally, on the top of the data or the program itself.

​

  • This will lead to unpredictable results, to say the least. Also, there will be no error message to warn the programmer of going beyond the array size. In some cases, the program may hang.

​

23 of 82

2D ARRAYS

  • 2D array can be defined as an array of arrays. The 2D array is organized as matrices which can be represented as the collection of rows and columns.

24 of 82

How to declare 2D Array

  • The syntax of declaring two dimensional array is very much similar to that of a one dimensional array, given as follows.
  • int arr[max_rows][max_columns];   
  1. for ( int i=0; i<n ;i++)  
  2. {  
  3.     for (int j=0; j<n; j++)   
  4.     {  
  5.         a[i][j] = 0;   
  6.     }  
  7. }  

25 of 82

Initializing 2D Arrays

The syntax to declare and initialize the 2D array is given as follows.

int arr[2][2] = {0,1,2,3};   

The number of elements that can be present in a 2D array will always be equal to (number of rows * number of columns).

26 of 82

Initializing 2D Arrays

  1. #include <stdio.h>  
  2. void main ()  
  3. {  
  4.     int arr[3][3],i,j;   
  5.     for (i=0;i<3;i++)  
  6.     {  
  7.         for (j=0;j<3;j++)  
  8.         {  
  9.             printf("Enter a[%d][%d]: ",i,j);              
  10.             scanf("%d",&arr[i][j]);  
  11.         }  
  12.     }  
  13.     printf("\n printing the elements ....\n");   
  14.     for(i=0;i<3;i++)  
  15.     {  
  16.         printf("\n");  
  17.         for (j=0;j<3;j++)  
  18.         {  
  19.             printf("%d\t",arr[i][j]);  
  20.         }  
  21.     }  
  22. }  

27 of 82

Calculating the Address of the random element of a 2D array

Row Major Order

If array is declared by a[m][n] where m is the number of rows while n is the number of columns, then address of an element a[i][j] of the array stored in row major order is calculated as,

Address(a[i][j]) = B. A. + ([i-lower bound of row index] * n + [j-lower bound of column index]) * size   

where, B. A. is the base address or the address of the first element of the array a[0][0] .

Example :

a[10...30, 55...75], base address of the array (BA) = 0, 

size of an element = 4 bytes .   

Find the location of a[15][68].   

  

Address(a[15][68]) = 0 + ((15 - 10) x (75 - 55 + 1) + (68 - 55)) x 4  

  = (5 x 21 + 13) x 4  

= 105 x 4   

= 420 answer   

28 of 82

Calculating the Address of the random element of a 2D array

Column major order

If array is declared by a[m][n] where m is the number of rows while n is the number of columns, then address of an element a[i][j] of the array stored in row major order is calculated as,

Address(a[i][j]) = (([j-lower bound of column index]*m)+[i-lower bound of row index])*Size + BA   

where BA is the base address of the array.

m=20+5-1=24

Example:

A [-5 ... +20][20 ... 70], BA = 1020, Size of element = 8 bytes. 

Find the location of a[0][30].   

  

Address 

[A[0][30]) = ((30-20) x 24 + 5)  x 8 + 1020   =  245 x 8 + 1020 = 2980 bytes   

29 of 82

Calculating the Address of the random element of a 2D array

30 of 82

Applications of Array Data Structure:

Below are some applications of arrays.

  • Arrays are used to implement data structures like a stack, queue, etc.
  • Arrays are used for matrices and other mathematical implementations.
  • Arrays are used in lookup tables in computers.
  • Arrays can be used for CPU scheduling.

31 of 82

Applications of Array Data Structure:

Real-Time Applications of Array:

  • Contact lists on mobile phones.
  • Matrices use arrays which are used in different fields like image processing, computer graphics, and many more.
  • Arrays are used in online ticket booking portals.
  • Pages of book.
  • IoT applications use arrays as we know that the number of values in an array will remain constant, and also that the accessing will be faster.
  • It is also utilised in speech processing, where each speech signal is represented by an array.
  • The viewing screen of any desktop/laptop is also a multidimensional array of pixels.

32 of 82

Applications of Array Data Structure:

Applications of Array in C:

  • Arrays are used as the base of all sorting algorithms.
  • Arrays are used to implement other DS like a stack, queue, etc.
  • Used for implementing matrices. 
  • Data structures like trees also sometimes use the array implementation since arrays are easier to handle than pointers. For example, a segment tree uses array implementation.
  • Binary search trees and balanced binary trees are used in data structures such as a heap, map, and set, which can be built using arrays.
  • Graphs are also implemented as arrays in the form of an adjacency matrix.

33 of 82

Sparse Matrices in Data Structure

  • A matrix will be a sparse matrix if most of the elements of it is 0.
  • Another definition is, a matrix with a maximum of 1/3 non-zero elements (roughly 30% of m x n) is known as sparse matrix.

34 of 82

Sparse Matrices in Data Structure

  • We can store the information about the sparse matrices using table structure. Suppose we will create a table called X like below −

35 of 82

Sparse Matrices in Data Structure

Representation of sparse matrix

Now, let's see the representation of the sparse matrix. The non-zero elements in the sparse matrix can be stored using triplets that are rows, columns, and values. There are two ways to represent the sparse matrix that are listed as follows -

  • Array representation
  • Linked list representation

36 of 82

Sparse Matrices in Data Structure

Array representation of the sparse matrix

Representing a sparse matrix by a 2D array leads to the wastage of lots of memory. This is because zeroes in the matrix are of no use, so storing zeroes with non-zero elements is wastage of memory. To avoid such wastage, we can store only non-zero elements. If we store only non-zero elements, it reduces the traversal time and the storage space.

In 2D array representation of sparse matrix, there are three fields used that are named as -

37 of 82

Sparse Matrices in Data Structure

Example -

Let's understand the array representation of sparse matrix with the help of the example given below -

Consider the sparse matrix -

In the figure, we can observe a 5x4 sparse matrix containing 7 non-zero elements and 13 zero elements. The above matrix occupies 5x4 = 20 memory space. Increasing the size of matrix will increase the wastage space.

38 of 82

Sparse Matrices in Data Structure

The tabular representation of the above matrix is given below -

39 of 82

Sparse Matrices in Data Structure

Linked List representation of the sparse matrix

In a linked list representation, the linked list data structure is used to represent the sparse matrix. The advantage of using a linked list to represent the sparse matrix is that the complexity of inserting or deleting a node in a linked list is lesser than the array.

Unlike the array representation, a node in the linked list representation consists of four fields. The four fields of the linked list are given as follows -

  • Row - It represents the index of the row where the non-zero element is located.
  • Column - It represents the index of the column where the non-zero element is located.
  • Value - It is the value of the non-zero element that is located at the index (row, column).
  • Next node - It stores the address of the next node.

40 of 82

Sparse Matrices in Data Structure

The node structure of the linked list representation of the sparse matrix is shown in the below image -

41 of 82

Sparse Matrices in Data Structure

Example -

Let's understand the linked list representation of sparse matrix with the help of the example given below -

Consider the sparse matrix -

In the figure, we can observe a 4x4 sparse matrix containing 5 non-zero elements and 11 zero elements. Above matrix occupies 4x4 = 16 memory space. Increasing the size of matrix will increase the wastage space.

42 of 82

Multidimensional Array in Data Structure

Multidimensional Arrays

A multidimensional array in MATLAB is an array with more than two dimensions. In a matrix, the two dimensions are represented by rows and columns.

         

Each element is defined by two subscripts, the row index and the column index. Multidimensional arrays are an extension of 2-D matrices and use additional subscripts for indexing. A 3-D array, for example, uses three subscripts. The first two are just like a matrix, but the third dimension represents pages or sheets of elements.

            

43 of 82

LINKED LIST

A linked list is a sequence of data structures, which are connected together via links.

Linked List is a sequence of links which contains items. Each link contains a connection to another link. Linked list is the second most-used data structure after array. Following are the important terms to understand the concept of Linked List.

  • Link − Each link of a linked list can store a data called an element.
  • Next − Each link of a linked list contains a link to the next link called Next.
  • LinkedList − A Linked List contains the connection link to the first link called First.

44 of 82

LINKED LIST

Types of Linked List

Following are the various types of linked list.

  • Linear Linked List − Item navigation is forward only.
  • Doubly Linked List − Items can be navigated forward and backward.
  • Circular Linked List − Last item contains link of the first element as next and the first element has a link to the last element as previous.
  • Circular Doubly Linked List

​

Basic Operations

Following are the basic operations supported by a list.

  • Insertion − Adds an element at the beginning of the list.
  • Deletion − Deletes an element at the beginning of the list.
  • Display − Displays the complete list.
  • Search − Searches an element using the given key.
  • Delete − Deletes an element using the given key.

​

45 of 82

SINGLY LINKED LIST

A singly linked list is a type of linked list that is unidirectional, that is, it can be traversed in only one direction from head to the last node (tail).

Each element in a linked list is called a node. A single node contains data and a pointer to the next node which helps in maintaining the structure of the list.

46 of 82

SINGLY LINKED LIST

1. Creation of a Singly Linked List

Let us assume that PTR, CPT, TPT are user defined working pointer variable which contain the address of next node.

​

Step 1: PTR=AVAIL

AVAIL=LINK(AVAIL)

Read INFO(PTR)

First=PTR

Step 2: CH=‘Y’

Step 3: Repeat Step 4 to 5 while CH==‘Y’

Step 4: CPT=AVAIL

AVAIL=LINK(AVAIL)

Read INFO(CPT)

LINK(PTR)=CPT

PTR=CPT

Step 5: Read Choice <Y/N> into CH for more nodes

Step 6: LINK(PTR)=Null

Step 7: Stop

​

47 of 82

SINGLY LINKED LIST

Creation of a Singly Linked List

Let us assume that PTR, CPT, TPT are user defined working pointer variable which contain the address of next node.

​

Step 1: PTR=AVAIL

AVAIL=LINK(AVAIL)

Read INFO(PTR)

First=PTR

Step 2: CH=‘Y’

Step 3: Repeat Step 4 to 5 while CH==‘Y’

Step 4: CPT=AVAIL

AVAIL=LINK(AVAIL)

Read INFO(CPT)

LINK(PTR)=CPT

PTR=CPT

Step 5: Read Choice <Y/N> into CH for more nodes

Step 6: LINK(PTR)=Null

Step 7: Stop

​

48 of 82

SINGLY LINKED LIST

Node Creation

struct node   

{  

    int data;   

    struct node *next;  

};  

struct node *head, *ptr;   

ptr = (struct node *)malloc(sizeof(struct node *));  

​

49 of 82

SINGLY LINKED LIST

Traversing of a singly Linked List

​

Algorithm:

  1. PTR=First
  2. Repeat Step 3 & 4 while LINK(PTR)!=Null
  3. Print INFO(PTR)
  4. PTR=LINK(PTR)
  5. STOP

​

50 of 82

INSERTION IN SINGLY LINKED LIST

I. Insertion at the beginning

​

Algorithm:

Step 1: If AVAIL==NULL then write link list is Overflow & Stop

Step 2: PTR=AVAIL

AVAIL=LINK(AVAIL)

Read INFO(PTR)

Step 3: LINK(PTR)=FIRST

FIRST=PTR

Step 4: STOP

51 of 82

INSERTION IN SINGLY LINKED LIST

II. Insertion at the End

​

Algorithm:

Step 1: If AVAIL==NULL then write link list is Overflow & Stop

Step 2: PTR=AVAIL

AVAIL=LINK(AVAIL)

Read INFO(PTR)

Step 3: CPT=FIRST

Step 4: Repeat Step 5 while LINK(CPT)!=NULL

Step 5: CPT=LINK(CPT)

Step 6: LINK(CPT)=PTR

LINK(PTR)=NULL

Step 7: Stop

52 of 82

INSERTION IN SINGLY LINKED LIST

III. Insertion at a given location

​

Algorithm:

Step 1: If AVAIL==NULL then write link list is Overflow & Stop

Step 2: Read DATA as information of node after which insertion will be made

Step 3: PTR=AVAIL

AVAIL=LINK(AVAIL)

Read INFO(PTR)

Step 4: CPT=FIRST

Step 5: Repeat Step 6 while INFO(CPT)!=DATA

Step 6: CPT=LINK(CPT)

Step 7: LINK(PTR)=LINK(CPT)

LINK(CPT)=PTR

Step 8: Stop

53 of 82

DELETION IN SINGLY LINKED LIST

I. Deletion from the beginning

​

Algorithm:

Step 1: If FIRST==NULL then write Underflow & Stop

Step 2: PTR=FIRST

FIRST=LINK(PTR)

Step 3: LINK(PTR)=AVAIL

AVAIL=PTR

Step 4: STOP

54 of 82

DELETION IN SINGLY LINKED LIST

II. Deletion from the End

​

Algorithm:

Step 1: If FIRST==NULL then write Underflow & Stop

Step 2: PTR=FIRST

Step 3: Repeat Step 4 while LINK(PTR)!=NULL

Step 4: CPT=PTR

PTR=LINK(PTR)

Step 5: LINK(CPT)=NULL

Step 6: LINK(PTR)=AVAIL

AVAIL=PTR

Step 7: Stop

55 of 82

DELETION IN SINGLY LINKED LIST

III. Deletion of given INFO Node

​

Algorithm:

Step 1: If FIRST==NULL then write Underflow & Stop

Step 2: Read DATA as information of node to be deleted

Step 3: PTR=FIRST

Step 4: Repeat Step 5 while INFO(PTR)!=DATA

Step 5: CPT=PTR

PTR=LINK(PTR)

Step 6: LINK(CPT)=LINK(PTR)

Step 7: LINK(PTR)=AVAIL

AVAIL=PTR

Step 8: Stop

56 of 82

CIRCULAR LINKED LIST

Circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or doubly circular linked list.

57 of 82

CREATION OF CIRCULAR LINKED LIST

1. PTR🡨AVAIL

AVAIL 🡨 LINK(AVAIL)

READ INFO(PTR)

FIRST 🡨 PTR

CH=’Y’

2. Repeat Step 3 to 4 while CH=’Y’

3. CPT 🡨 AVAIL

AVAIL 🡨 LINK(AVAIL)

READ INFO(CPT)

LINK(PTR) 🡨 CPT

PTR 🡨 CPT

4. Press Y or N for more nodes

  1. LINK(PTR) 🡨 FIRST
  2. STOP

​

58 of 82

TRAVERSING OF CIRCULAR LINKED LIST

  1. PTR🡨FIRST

Process INFO(PTR)

PTR 🡨 LINK(PTR)

  1. Repeat Step 3 while PTR!=FIRST
  2. Process INFO(PTR)

PTR 🡨 LINK(PTR)

4. STOP

​

59 of 82

INSERTION IN CIRCULAR LINKED LIST

  1. At the Beginning

​

Algorithm

  1. If AVAIL==NULL then Linked List is OVERFLOW & STOP

2. PTR🡨AVAIL

AVAIL 🡨 LINK(AVAIL)

READ INFO(PTR)

  1. CPT 🡨 FIRST
  2. Repeat Step 5 while LINK(CPT)!=FIRST
  3. CPT 🡨 LINK(CPT)
  4. LINK(PTR)🡨FIRST

FIRST🡨PTR

LINK(CPT)🡨FIRST

7. Stop

​

​

​

​

60 of 82

INSERTION IN CIRCULAR LINKED LIST

II. At the End

​

Algorithm

  1. If AVAIL==NULL then Linked List is OVERFLOW & STOP

2. PTR🡨AVAIL

AVAIL 🡨 LINK(AVAIL)

READ INFO(PTR)

  1. CPT 🡨 FIRST
  2. Repeat Step 5 while LINK(CPT)!=FIRST
  3. CPT 🡨 LINK(CPT)
  4. LINK(CPT)🡨PTR
  5. LINK(PTR)🡨FIRST
  6. Stop

​

​

​

61 of 82

DELETION IN CIRCULAR LINKED LIST

  1. From the Beginning

​

Algorithm

  1. If FIRST==NULL then Linked List is UNDERFLOW & STOP

2 CPT 🡨 FIRST

  1. Repeat Step 4 while LINK(CPT)!=FIRST
  2. CPT 🡨 LINK(CPT)
  3. PTR🡨FIRST

FIRST🡨LINK(PTR)

LINK(CPT)🡨FIRST

6. LINK(PTR)🡨AVAIL

AVAIL🡨PTR

7. Stop

​

​

​

62 of 82

DELETION IN CIRCULAR LINKED LIST

II. From the End

​

Algorithm

  1. If FIRST==NULL then Linked List is UNDERFLOW & STOP

2 CPT 🡨 FIRST

  1. Repeat Step 4 while LINK(CPT)!=FIRST
  2. PTR🡨CPT

CPT 🡨 LINK(CPT)

5. LINK(PTR)🡨FIRST

6. LINK(CPT)🡨AVAIL

AVAIL🡨CPT

7. Stop

​

​

​

63 of 82

DOUBLY LINKED LIST

Doubly linked list

Doubly linked list is a complex type of linked list in which a node contains a pointer to the previous as well as the next node in the sequence. Therefore, in a doubly linked list, a node consists of three parts: node data, pointer to the next node in sequence (next pointer) , pointer to the previous node (previous pointer). A sample node in a doubly linked list is shown in the figure.

​

�

64 of 82

CREATION OF DOUBLY LINKED LIST

Algorithm

  1. PTR🡨AVAIL

AVAIL🡨RPT(AVAIL)

READ INFO(PTR)

LPT(PTR)🡨NULL

FIRST🡨PTR

  1. STORE ‘Y’ to CH
  2. Repeat Step 4 to 5 while CH=’Y’

4. (a) CPT🡨AVAIL

AVAIL🡨RPT(AVAIL)

READ INFO(CPT)

(b) RPT(PTR)🡨CPT

LPT(CPT)🡨PTR

PTR🡨CPT

  1. Input Choice <Y/N> for more nodes
  2. RPT(PTR)🡨NULL
  3. STOP

65 of 82

FORWARD TRAVERSING OF DOUBLY LINKED LIST

Algorithm

  1. PTR🡨FIRST
  2. Repeat Step 3 to 4 while RPT(PTR)!=NULL
  3. Process INFO(PTR)
  4. PTR🡨RPT(PTR)
  5. STOP

66 of 82

BACKWARD TRAVERSING OF DOUBLY LINKED LIST

Algorithm

  1. PTR🡨FIRST
  2. Repeat Step 3 to 4 while RPT(PTR)!=NULL
  3. PTR🡨RPT(PTR)
  4. Repeat Step 5 to 6 while LPT(PTR)!=NULL
  5. Process INFO(PTR)
  6. PTR🡨LPT(PTR)
  7. STOP

67 of 82

INSETION IN DOUBLY LINKED LIST

  1. At the Beginning

​

Algorithm

  1. If AVAIL=NULL then Write OVERFLOW & STOP
  2. PTR🡨AVAIL

AVAIL🡨RPT(AVAIL)

READ INFO(PTR)

  1. RPT(PTR)🡨FIRST

LPT(FIRST)🡨PTR

LPT(PTR)🡨NULL

FIRST🡨PTR

4. STOP

​

​

68 of 82

INSETION IN DOUBLY LINKED LIST

II. At the End

​

Algorithm

  1. If AVAIL=NULL then Write OVERFLOW & STOP
  2. PTR🡨AVAIL

AVAIL🡨RPT(AVAIL)

READ INFO(PTR)

  1. CPT🡨FIRST
  2. Repeat Step 5 while RPT(CPT)!=NULL
  3. CPT🡨RPT(CPT)
  4. RPT(CPT)🡨PTR

LPT(PTR)🡨CPT

RPT(PTR)🡨NULL

7. STOP

​

​

69 of 82

INSETION IN DOUBLY LINKED LIST

III. After a Given Node

​

Algorithm

  1. If AVAIL=NULL then Write OVERFLOW & STOP
  2. PTR🡨AVAIL

AVAIL🡨RPT(AVAIL)

READ INFO(PTR)

  1. Read DATA as information after which insertion will be made
  2. CPT🡨FIRST
  3. Repeat Step 6 while INFO(CPT)!=DATA
  4. CPT🡨RPT(CPT)
  5. TPT🡨RPT(CPT)

RPT(CPT)🡨PTR

LPT(PTR)🡨CPT

RPT(PTR)🡨TPT

LPT(TPT)🡨PTR

8. STOP

70 of 82

DELETION IN DOUBLY LINKED LIST

I. From the Beginning

​

Algorithm

  1. If FIRST=NULL then Write UNDERFLOW & STOP
  2. PTR🡨FIRST

FIRST🡨RPT(PTR)

LPT(FIRST)🡨NULL

  1. RPT(PTR)🡨AVAIL

AVAIL🡨PTR

4. STOP

71 of 82

DELETION IN DOUBLY LINKED LIST

II. From the End

​

Algorithm

  1. If FIRST=NULL then Write UNDERFLOW & STOP
  2. PTR🡨FIRST
  3. Repeat Step 4 while RPT(PTR)!=NULL
  4. PTR🡨RPT(PTR)
  5. CPT🡨LPT(PTR)

RPT(CPT)🡨NULL

  1. RPT(PTR)🡨AVAIL

AVAIL🡨PTR

4. STOP

72 of 82

DELETION IN DOUBLY LINKED LIST

III. If Specific Node is Given

​

Algorithm

  1. If FIRST=NULL then Write UNDERFLOW & STOP
  2. Read DATA as information of node to be deleted
  3. PTR🡨FIRST
  4. Repeat Step 5 while INFO(PTR)!=DATA
  5. PTR🡨RPT(PTR)
  6. CPT🡨LPT(PTR)

TPT🡨RPT(PTR)

RPT(CPT)🡨TPT

LPT(TPT)🡨CPT

7. RPT(PTR)🡨AVAIL

AVAIL🡨PTR

8. STOP

73 of 82

DOUBLY CIRCULAR LINKED LIST

Circular doubly linked list is a more complexed type of data structure in which a node contain pointers to its previous node as well as the next node. Circular doubly linked list doesn't contain NULL in any of the node. The last node of the list contains the address of the first node of the list. The first node of the list also contain address of the last node in its previous pointer.

A circular doubly linked list is shown in the following figure.

74 of 82

MEMORY MANAGEMENT OF CIRCULAR DOUBLY LINKED LIST

75 of 82

CREATION OF CIRCULAR DOUBLY LINKED LIST

  1. PTR🡨AVAIL

AVAIL🡨RPT(AVAIL)

AVAIL🡨LPT(AVAIL)

Read INFO(PTR)

LPT(PTR)🡨PTR

RPT(PTR)🡨PTR

FIRST🡨PTR

2. STORE ‘Y’ to CH

  1. Repeat Step 4 to 5 while CH=‘Y’
  2. (a) CPT🡨AVAIL

AVAIL🡨RPT(AVAIL)

Read INFO(CPT)

(b) RPT(PTR)🡨CPT

LPT(CPT)🡨PTR

PTR🡨CPT

5. Input Choice <Y/N> for more nodes

6. RPT(PTR)🡨FIRST

LPT(FIRST)🡨PTR

7. Stop

76 of 82

INSERTION IN CIRCULAR DOUBLY LINKED LIST

  1. At the Beginning

​

  1. If AVAIL=NULL then write OVERFLOW & STOP
  2. PTR🡨AVAIL

AVAIL🡨RPT(AVAIL)

AVAIL🡨LPT(AVAIL)

Read INFO(PTR)

FIRST🡨PTR

  1. TPT🡨LPT(FIRST)
  2. RPT(PTR)🡨First

LPT(FIRST)🡨PTR

  1. LPT(PTR)🡨TPT

RPT🡨TPT(PTR)

  1. FIRST🡨PTR
  2. Stop

77 of 82

INSERTION IN CIRCULAR DOUBLY LINKED LIST

II. At the Beginning

​

  1. If AVAIL=NULL then write OVERFLOW & STOP
  2. PTR🡨AVAIL

AVAIL🡨RPT(AVAIL)

AVAIL🡨LPT(AVAIL)

Read INFO(PTR)

TPT🡨LPT(FIRST)

  1. TPT🡨LPT(FIRST)
  2. RPT(TPT)🡨PTR

LPT(PTR)🡨TPT

5. RPT(PTR)🡨FIRST

LPT(FIRST)🡨PTR

  1. Stop

78 of 82

DELETION IN CIRCULAR DOUBLY LINKED LIST

I. At the Beginning

​

  1. If FIRST=NULL then write UNDERFLOW & STOP
  2. TPT🡨FIRST

PTR🡨RPT(FIRST)

CPT🡨LPT(FIRST)

3. LPT(PTR)🡨CPT

RPT(CPT)🡨PTR

4. FIRST🡨PTR

5. LPT(TPT)🡨AVAIL

RPT(TPT)🡨AVAIL

AVAIL🡨TPT

  1. Stop

79 of 82

DELETION IN CIRCULAR DOUBLY LINKED LIST

II. At the End

​

  1. If FIRST=NULL then write UNDERFLOW & STOP
  2. PTR🡨LPT(FIRST)

CPT🡨LPT(PTR)

3. LPT(FIRST)🡨CPT

RPT(CPT)🡨FIRST

4. LPT(PTR)🡨AVAIL

RPT(PTR)🡨AVAIL

AVAIL🡨PTR

  1. Stop

80 of 82

DELETION IN CIRCULAR DOUBLY LINKED LIST

II. At the End

​

  1. If FIRST=NULL then write UNDERFLOW & STOP
  2. PTR🡨LPT(FIRST)

CPT🡨LPT(PTR)

3. LPT(FIRST)🡨CPT

RPT(CPT)🡨FIRST

4. LPT(PTR)🡨AVAIL

RPT(PTR)🡨AVAIL

AVAIL🡨PTR

  1. Stop

81 of 82

​

// Fibonacci Series using Recursion

#include <stdio.h>

int fib(int n)

{

if (n <= 1)

return n;

return fib(n - 1) + fib(n - 2);

}

int main()

{

int n = 9;

printf("%d", fib(n));

getchar();

return 0;

}

82 of 82

#include<stdio.h>

long int multiplyNumbers(int n);

int main() {

int n;

printf("Enter a positive integer: ");

scanf("%d",&n);

printf("Factorial of %d = %ld", n, multiplyNumbers(n));

return 0;

}

​

long int multiplyNumbers(int n) {

if (n>=1)

return n*multiplyNumbers(n-1);

else

return 1;

}