SINGLY LINKED LIST

 SINGLY LINKED LIST

The singly linked list is a data structure that contains two parts, i.e., one is the data part, and the other one is the address part, which contains the address of the next or the successor node. The address part in a node is also known as a pointer. The pointer that holds the address of the initial node is known as a head pointer.

Operations on Singly Linked List:

 There are various operations which can be performed on singly linked list. A list of all such operations is given below. 

Node Creation:

struct node 

{

                    int data;

struct node *next; 

}

struct node *head, *ptr; 

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

OPERATION ON ARRAY

 OPERATIONS ON ARRAYS:

There are a number of operations that can be preformed on arrays. These operations include:

1. Traversing an array
2. Inserting an element in an array
3. Searching an element in an array
4. Deleting an element from an array
5. Merging two arrays
6. Sorting an array in ascending or descending order

1. Traversing an array:

Traversing the data elements of an array A can include printing every element, counting the total number of elements, or performing any process on these elements.

Algorithm for array traversal

Programming Examples:

https://www.programiz.com/c-programming/online-compiler/

Inserting an Element in an Array:

Algorithm to Insert an Element in the Middle of an Array

The algorithm INSERT will be declared as INSERT (A, N, POS, VAL). The arguments are

(a) A, the array in which the element has to be inserted

(b) N, the number of elements in the array

(c) POS, the position at which the element has to be inserted

(d) VAL, the value that has to be inserted

1.Write a program to insert a number at a given location in an array.

#include <stdio.h>

void main()

{

    int array[100];

    int i, n, x, pos;

    printf("Enter the number of elements in the array \n");

    scanf("%d", &n);

    printf("Enter the elements \n");

 

    for (i = 0; i < n; i++)

    {

        scanf("%d", &array[i]);

    }

 

    printf("Input array elements are: \n");

    for (i = 0; i < n; i++)

    {

        printf("%d ", array[i]);

    }

    printf("\nEnter the new element to be inserted: ");

    scanf("%d", &x);

    printf("Enter the position where element is to be inserted: ");

    scanf("%d", &pos);

 

    //shift all elements 1 position forward from the place

    //where element needs to be inserted

    n=n+1;

    for(i = n-1; i >= pos; i--)

        array[i]=array[i-1];

 

    array[pos-1]=x;

 //Insert the element x on the specified position

     //print the new array

    for (i = 0; i < n; i++)

    {

        printf("%d ", array[i]);

    }

}

STACK

 STACK

A Stack is linear data structure. A stack is a list of elements in which an element may be inserted or deleted only at one end, called the top of the stack. Stack principle is LIFO (last in, first out). 

 As the items can be added or removed only from the top i.e. the last item to be added to a stack is the first item to be removed.

Operations on stack: 

The two basic operations associated with stacks are: 1. Push 2. Pop 

While performing push and pop operations the following test must be conducted on the stack. a) Stack is empty or not b) stack is full or not 

1. Push: Push operation is used to add new elements in to the stack. At the time of addition first check the stack is full or not. If the stack is full it generates an error message "stack overflow". 

2. Pop: Pop operation is used to delete elements from the stack. At the time of deletion first check the stack is empty or not. If the stack is empty it generates an error message "stack underflow".

3.Peek Operation:Peek is an operation that returns the value of the topmost element of the stack without deleting it from the stack.

Representation of Stack (or) Implementation of stack:

The stack should be represented in two ways: 

1. Stack using array 

2. Stack using linked list

LINKED LIST

 LINKED LIST

The major drawback of an array is that the number of elements must be known in advance. Hence an alternative approach was required. This give rise to the concept called linked list

   

Linked list is a dynamic data structure in which elements (called nodes) form a sequential list.

• A node contains two fields i.e. data stored at that particular address and the pointer which contains the address of the next node in the memory. 
• The last node of the list contains pointer to the null.

Array contains following limitations:

1. The size of array must be known in advance before using it in the program. 

2. Increasing size of the array is a time taking process. It is almost impossible to expand the

size of the array at run time. 

3. All the elements in the array need to be contiguously stored in the memory. Inserting any

element in the array needs shifting of all its predecessors.

 Using linked list is useful because, 

1. It allocates the memory dynamically. All the nodes of linked list are non-contiguously stored in the memory and linked together with the help of pointers. 

2. Sizing is no longer a problem since we do not need to define its size at the time of

declaration. List grows as per the program's demand and limited to the available memory

space.

Differences between the array and linked list :

ARRAYS

UNIT-1: INTRODUCTION TO DATA STRUCTURE

 INTRODUCTION TO DATA STRUCTURE

DEFINITION:

1. A data structure is an arrangement of data in a computer's memory (or sometimes on disk).
2. Data structure is the structural representation of logical relationships between elements of data.
3. A data structure is a group of data elements grouped together under one name. These data element known as members can have different types and different lengths.
4.  Data structure means how the data is organised in memory. There are different kinds of data structures. Some are used to store the data of same type and some are used to store different types of data. Data structure is a combination of two or more data type elements
5. A data structure is a logical mode of a particular organisation of data. The choice of particular data structure depends on the following consideration:

• It must able to represent the inherent relationship of the data in real world.
• It must be simple enough so that it can process efficiently as when necessary