Ds Lab Manual

2
ACE
AMBALA COLLEGE OF ENGINEERING AND APPLIED RESEARCHDEVSTHALI(AMBALA)

Subject: DATA STRUCTURES(Pr)
LABORATORY MANUAL
PRACTICAL EXPERIMENT INSTRUCTION SHEET

LABORATORY MANUAL NO. . : ACE- CSE-203 E
LABORATORY :
ISSUE NO. : 00
ISSUE DATE :
SEMESTER : 3rd
PAGE: 01 OF 02
MASTER LIST OF EXPERIMENT

SN
EXPERIMENT NO. ACE-WI-
EXPERIMENT DESCRIPTION
REV. NO.
REV. DATE
PAGE NO.
Implement BUBBLE SORT algorithm on a given array of numbers. Implement SELECTION SORT algorithm on a given array of numbers. Implement INSERTION SORT algorithm on a given array of numbers. Implement QUICK SORT algorithm on a given array of numbers. Implement LINEAR SEARCH algorithm on a given array of numbers. Implement BINARY SEARCH algorithm on a given array of numbers. Static implementation STACK algorithm. Dynamic implementation of STACK algorithm. Implement QUEUE algorithm on a given array of numbers. Implement conversion of INFIX to POSTFIX expression. Implement the EVALUATION of POSTFIX expression.
APPROVED BY: Prof. ARVIND SELWAL
11
13
15
18
19
9 10
9 10
21 23
11
11
26
PREPARED BY:ER.RAJEEV GOEL
ACE

LABORATORY MANUAL

LABORATORY :
ISSUE NO. : 00
ISSUE DATE :
SEMESTER : 3rd
PAGE: 01 of 02
12 13
12 13
Implement LINKED LIST data structure. Implement CIRCULAR LINKED LIST data structure.
27 31
ACE

LABORATORY MANUAL

LABORATORY :
ISSUE NO. : 00
ISSUE DATE :
SEMESTER : 3rd
PAGE: 01 OF 02
Aim: Implement BUBBLE SORT algorithm on a given array of numbers.

Bubble sort is a simple sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort. Step-by-step example Let us take the array of numbers "5 1 4 2 8", and sort the array from lowest number to greatest number using bubble sort algorithm. In each step, elements written in bold are being compared. First Pass: ( 5 1 4 2 8 ) ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps them. ( 1 5 4 2 8 ) ( 1 4 5 2 8 ), Swap since 5 > 4 ( 1 4 5 2 8 ) ( 1 4 2 5 8 ), Swap since 5 > 2 ( 1 4 2 5 8 ) ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them. Second Pass: (14258) (14258) ( 1 4 2 5 8 ) ( 1 2 4 5 8 ), Swap since 4 > 2 (12458) (12458) (12458) (12458) Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted. Third Pass: (12458) (12458) (12458) (12458) (12458) (12458) (12458) (12458) Finally, the array is sorted, and the algorithm can terminate
ALGORITHM:
procedure bubbleSort( A : list of sortable items ) defined as: n := length( A ) do swapped := false for each i in 0 to n - 1 inclusive do: if A[ i ] > A[ i + 1 ] then
swap( A[ i ], A[ i + 1 ] ) swapped := true end
ACE

LABORATORY MANUAL

LABORATORY :
ISSUE NO. : 00
ISSUE DATE :
SEMESTER : 3rd
PAGE: 02 OF 02
n := n - 1
while swapped
end procedure FLOWCHART
ACE

LABORATORY MANUAL

LABORATORY :
ISSUE NO. : 00
ISSUE DATE :
SEMESTER : 3rd
PAGE: 01 OF 03
Aim: Implement SELECTION SORT algorithm on a given array of numbers.

Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations.
Algorithm
The algorithm works as follows: 1. Find the minimum value in the list 2. Swap it with the value in the first position 3. Repeat the steps above for the remainder of the list (starting at the second position and advancing each time) Effectively, the list is divided into two parts: the sublist of items already sorted, which is built up from left to right and is found at the beginning, and the sublist of items remaining to be sorted, occupying the remainder of the array. // selection sort function module in C // Source: http://en.wikipedia.org/wiki/Selection_sort // This code is licensed under the GNU Free Documentation License. // It is from the Wikipedia article "Selection sort" dated 2006-11-07. { int i, j, min, temp; for (i = 0; i < count - 1; i++) { /* find the minimum */ min = i; for (j = i+1; j < count; j++) { if (data[j] < data[min]) { min = j; } } /* swap data[i] and data[min] */ temp = data[i]; data[i] = data[min];
PREPARED BY:ER.RAJEEV GOEL APPROVED BY: Prof. ARVIND SELWAL
data[min] = temp; } AMBALA COLLEGE OF ENGINEERING AND APPLIED RESEARCHACE DEVSTHALI(AMBALA)

LABORATORY MANUAL

LABORATORY :
ISSUE NO. : 00
ISSUE DATE :
SEMESTER : 3rd
PAGE: 02 OF 03
FLOWCHART
ACE

LABORATORY MANUAL

LABORATORY :
ISSUE NO. : 00
ISSUE DATE :
SEMESTER : 3rd
PAGE: 03 OF 03
Performance
Class Data structure Worst case performance Best case performance Average case performance Worst case space complexity Sorting algorithm Array
O(n2) O(n) O(n2) O(1) auxiliary
ACE

LABORATORY MANUAL

LABORATORY :
ISSUE NO. : 00
ISSUE DATE :
SEMESTER : 3rd
PAGE: 01 OF 02
Aim: Implement INSERTION SORT algorithm on a given array of numbers.

Insertion sort is a simple sorting algorithm, a comparison sort in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. Example: Linear insertion is easier to explain and let's start with it. We will assume that we are sorting an array in ascending order. Insertion sort always maintains two zones in the array to be sorted: sorted and unsorted. At the beginning the sorted zone consist of one element. On each step the algorithms expand it by one element inserting the first element from the unsorted zone in the proper place in the sorted zone and shifting all larger elements one slot down. It is an algorithms that many people intuitively use for sorting cards and it is very easy to illustrate on the deck of cards. Here is an example (sorted zone is in blue, unsorted is in red): 5 | 3 1 7 0 -> 3 5 | 1 7 9 -> 1 3 5 | 7 9 -> 1 3 5 7 | 9 -> 1 3 5 7 9 Since multiple keys with the same value are placed in the sorted array in the same order that they appear in the input array, insertion sort is stable. ALGORITHM: insertionSort(array A) begin for i := 1 to length[A]-1 do begin value := A[i]; j := i - 1; while j >= 0 and A[j] > value do begin A[j + 1] := A[j]; j := j - 1; end; A[j + 1] := value; end; end;
10
ACE

LABORATORY MANUAL

LABORATORY :
ISSUE NO. : 00
ISSUE DATE :
SEMESTER : 3rd
PAGE: 02 OF 02
Performance
Class Data structure Worst case performance Best case performance Average case performance Worst case space complexity Sorting algorithm Array
O(n2) O(n) O(n2) O(1) auxiliary
11
ACE

LABORATORY MANUAL

LABORATORY :
ISSUE NO. : 00
ISSUE DATE :
SEMESTER : 3rd
PAGE: 01 OF 02
Aim: Implement QUICK SORT algorithm on a given array of numbers..

Quicksort is a well-known sorting algorithm developed by C. A. R. Hoare that, on average, makes (nlogn) (big O notation) comparisons to sort n items. In the worst case, it makes (n2) comparisons, though if implemented correctly this behavior is rare. Typically, quicksort is significantly faster in practice than other (nlogn) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data, it is possible to make design choices which minimize the probability of requiring quadratic time. Quicksort (also known as "partition-exchange sort") is a comparison sort and, in efficient implementations, is not a stable sort. Algorithm The steps are: 1. Pick an element, called a pivot, from the list. 2. Reorder the list so that all elements which are less than the pivot come before the pivot and so that all elements greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation. 3. Recursively sort the sub-list of lesser elements and the sub-list of greater elements. The base case of the recursion are lists of size zero or one, which are always sorted.
procedure quicksort(array, left, right) if right > left select a pivot index (e.g. pivotIndex := (left+right)/2) pivotNewIndex := partition(array, left, right, pivotIndex) quicksort(array, left, pivotNewIndex - 1) quicksort(array, pivotNewIndex + 1, right) function partition(array, left, right, pivotIndex) pivotValue := array[pivotIndex] swap array[pivotIndex] and array[right] // Move pivot to end storeIndex := left for i from left to right - 1 // left i < right
12
if array[i] pivotValue AMBALA COLLEGE OF ENGINEERING AND APPLIED RESEARCHDEVSTHALI(AMBALA)

LABORATORY MANUAL
ACE

LABORATORY :
ISSUE NO. : 00
ISSUE DATE :
SEMESTER : 3rd
PAGE: 02 OF 02
swap array[i] and array[storeIndex] storeIndex := storeIndex + 1 swap array[storeIndex] and array[right] // Move pivot to its final place
return storeIndex
EXAMPLE:
Full example of quicksort on a random set of numbers. The boxed element is the pivot. It is always chosen as the last element of the partition.
13
ACE

LABORATORY MANUAL

LABORATORY MANUAL NO. . : ACE-WI-CO-211E
LABORATORY :
ISSUE NO. : 00
ISSUE DATE :
SEMESTER : 3rd
PAGE: 01 OF 02
Aim: Implement LINEAR SEARCH algorithm on a given array of numbers.

linear search or sequential search is a method for finding a particular value in a list, that consists in checking every one of its elements, one at a time and in sequence, until the desired one is found. Linear search is the the simplest search algorithm; it is a special case of brute-force search. Its worst case cost is proportional to the number of elements in the list; and so is its expected cost, if all list elements are equally likely to be searched for. Therefore, if the list has more than a few elements, other methods (such as binary search or hashing) may be much more efficient. EXAMPLE: an array of integers, like the following:
Figure %: The array we're searching Lets search for the number 3. We start at the beginning and check the first element in the array. Is it 3?
Figure %: Is the first value 3? No, not it. Is it the next element
Figure %: Is the second value 3? Not there either. The next element
Figure %: Is the third value 3? Not there either. Next
14
ACE

LABORATORY MANUAL

LABORATORY :
ISSUE NO. : 00
ISSUE DATE :
SEMESTER : 3rd
PAGE: 02 OF 02
ALGORITHM: Suppose an array A with elements indexed 0 to n1 is to be searched for a value x. The following pseudocode performs a forward search, returning n if the value is not found: i0 repeat this loop: if i n exit the loop; if A[i] = x then exit the loop; ii+1 return i.
If the value being sought occurs k times in the list, and all orderings of the list are equally likely, the expected number of comparisons is
Asymptotically, therefore, the worst-case cost and the expected cost of linear search are both O(n)
15
ACE

LABORATORY MANUAL

LABORATORY :
ISSUE NO. : 00
ISSUE DATE :
SEMESTER : 3rd
PAGE: 01 OF 03
Aim: Implement BINARY SEARCH algorithm on a given array of numbers

Binary search is an algorithm for locating the position of an element in a sorted list. It inspects the middle element of the sorted list: if equal to the sought value, then the position has been found; otherwise, the upper half or lower half is chosen for further searching based on whether the sought value is greater than or less than the middle element. The method reduces the number of elements needed to be checked by a factor of two each time, and finds the sought value if it exists in the list or if not determines "not present", in logarithmic time. A binary search is a divide and conquer search algorithm.
ALGORITHM low = 0 high = N while (low < high) { mid = low + ((high - low) / 2) if (A[mid] < value) low = mid + 1; else //can't be high = mid-1: here A[mid] >= value, //so high can't be < mid if A[mid] == value high = mid; } // high == low, using high or low depends on taste if ((low < N) && (A[low] == value)) return low // found else return -1 // not found
16
ACE

LABORATORY MANUAL

LABORATORY :
ISSUE NO. : 00
ISSUE DATE :
SEMESTER : 3rd
PAGE: 02 OF 03
FLOWCHART:
17
ACE

LABORATORY MANUAL

LABORATORY :
ISSUE NO. : 00
ISSUE DATE :
SEMESTER : 3rd
PAGE: 03 OF 03
18
PERFORMANCE
Class Data structure Worst case performance Best case performance Average case performance Worst case space complexity Searching Algorithm Array
O(lgn) O(1) O(lgn) O(1) auxiliary
ACE

LABORATORY MANUAL

ISSUE NO. : 00
SEMESTER : 3rd
EXPERIMENT NO. : ACE- CSE-203 E

LABORATORY : CENTRE-V
ISSUE DATE : PAGE : 01 OF 01
Aim: Static Implementation of STACK algorithm.

Stack is a last in, first out (LIFO) abstract data type and data structure. A stack can have any abstract data type as an element, but is characterized by only two fundamental operations: push
19
and pop. The push operation adds to the top of the list, hiding any items already on the stack, or initializing the stack if it is empty. The pop operation removes an item from the top of the list, and returns this value to the caller. A pop either reveals previously concealed items, or results in an empty list. STATIC IMPLEMENTATION(Using Array) PUSH OPERTION The push() operation is used both to initialize the stack, and to store values to it. It is responsible for changing the value of ps->size and for inserting a value into the ps->items[] array. In a responsible C implementation, it also checks whether the array is already fullif it is, storing a value to it will result in a segmentation fault, at least in C. void push(STACK *ps, int x) { if (ps->size == STACKSIZE) { fputs("Error: stack overflow\n", stderr); abort(); } else ps->items[ps->size++] = x; } POP OPERATION The pop() operation is responsible for removing a value from the stack, and decrementing the value of ps->size. A responsible C implementation will also check that the array is not already empty. If it is, popping a value from the array will result in another segmentation fault. int pop(STACK *ps) { if (ps->size == 0){ fputs("Error: stack underflow\n", stderr); abort(); } else return ps->items[--ps->size]; }
ACE

LABORATORY MANUAL

ISSUE NO. : 00
SEMESTER : 3rd
EXPERIMENT NO. : ACE- CSE-203 E

LABORATORY : CENTRE-V
Aim: Dynamic Implementation of STACK algorithm

20
The linked-list implementation is equally simple and straightforward. In fact, a stack linked-list is much simpler than most linked-list implementations: it requires that we implement a linkedlist where only the head node or element can be removed, or popped, and a node can only be inserted by becoming the new head node. Unlike the array implementation, our structure typedef corresponds not to the entire stack structure, but to a single node: typedef struct stack { int data; struct stack *next; } STACK; Such a node is identical to a typical linked-list node, at least to those that are implemented in C. PUSH OPERTION The push() operation both initializes an empty stack, and adds a new node to a non-empty one. It works by receiving a data value to push onto the stack, along with a target stack, creating a new node by allocating memory for it, and then inserting it into a linked list as the new head: void push(STACK **head, int value) { STACK *node = malloc(sizeof(STACK)); /* create a new node */ if (node == NULL){ fputs("Error: no space available for node\n", stderr); abort(); } else { /* initialize node */ node->data = value; node->next = empty(*head) ? NULL : *head; /* insert new head if any */ *head = node; } }
ACE

LABORATORY MANUAL

LABORATORY :
ISSUE NO. : 00
ISSUE DATE :
SEMESTER : 3rd
PAGE: 02 OF 02
POP OPERATION A pop() operation removes the head from the linked list, and assigns the pointer to the head to the previous second node. It check whether the list is empty before popping from it:
21
int pop(STACK **head) { if (empty(*head)) { /* stack is empty */ fputs("Error: stack underflow\n", stderr); abort(); } else { /* pop a node */ STACK *top = *head; int value = top->data; *head = top->next; free(top); return value;}
ACE

LABORATORY MANUAL

LABORATORT MANUAL NO. . : ACE- CSE-203 E
LABORATORY :
ISSUE NO. : 00
SEMESTER : 3rd
ISSUE DATE : PAGE : 01OF02
Aim: Implement QUEUE algorithm on a given array of numbers
22
Queue is a First-In-First-Out (FIFO) data structure. In a FIFO data structure, the first element added to the queue will be the first one to be removed. This is equivalent to the requirement that whenever an element is added, all elements that were added before have to be removed before the new element can be invoked. A queue is an example of a linear data structure. Queues provide services in computer science, transport and operations research where various entities such as data, objects, persons, or events are stored and held to be processed later. In these contexts, the queue performs the function of a buffer. Queues are common in computer programs, where they are implemented as data structures coupled with access routines, as an abstract data structure or in object-oriented languages as classes. Common implementations are circular buffers and linked lists.
QUEUE STRUCTURE D={d,F,A}

Where, d : Array or a node (structure) d = { a , FRONT, REAR } Here, a : Simple array or structure FRONT : Pointer to the front element of a queue REAR : Pointer to the rear element of a queue F : QINSERT, QDELETE, Q DISPLAY, QMODIFY A : QFULL, QEMPTY
Types of Queues

Linear Queue Circular Queue AMBALA COLLEGE OF ENGINEERING AND APPLIED RESEARCHDEVSTHALI(AMBALA)
LABORATORY MANUAL
ACE

LABORATORY :
ISSUE NO. : 00
ISSUE DATE :
SEMESTER : 3rd
PAGE: 02 OF 02
ALGORITHM LINEAR QUEUE

23 Procedure QINSERT(Q,F,MAX,X) : Given F and R, pointers to the front and rear elements of a queue. A QUEUE Q consisting of MAX elements and an element X. this procedure inserts X at the rear end of the queue prior to the first invocation of the procedure, F and R have been set to -1.
STEP 1: [Is front pointer properly set] if (F==R) then F <-- R <-- -1 STEP 2: [Check for overflow condition] if (R>=(MAX-1)) then write ('Error : Overflow') Return STEP 3: [Increment rear pointer] R <-- R+1 STEP 4: [Insert element] Q[R] <-- X Return Procedure QDELETE(Q,F,R) : Given F and R,the pointers to the front and rear elements of a queue respectively and the queue Q to which they correspond. This procedure delets and returns the element at the front end of the queue .Here X is a temporary variable. STEP 1: [Check for underflow condition] if (F>=R) then write('Error : Underflow'] Return STEP 2: [Increment the front pointer] F <-- F+1 STEP 3: [Delete element] Y <-- Q[F] Return Y
ACE

LABORATORY MANUAL

LABORATORY :
ISSUE NO. : 00
ISSUE DATE :
SEMESTER : 3rd
PAGE: 01 OF 03
Aim: Implement conversion of Infix to Postfix expression

24
The algorithm for the conversion is as follows :

Scan the Infix string from left to right. Initialise an empty stack. If the scannned character is an operand, add it to the Postfix string. If the scanned character is an operator and if the stack is empty Push the character to stack.
If the scanned character is an Operand and the stack is not empty, compare the precedence of the character with the element on top of the stack (topStack). If topStack has higher precedence over the scanned character Pop the stack else Push the scanned character to stack. Repeat this step as long as stack is not empty and topStack has precedence over the character.
Repeat this step till all the characters are scanned.
(After all characters are scanned, we have to add any character that the stack may have to the Postfix string.) If stack is not empty add topStack to Postfix string and Pop the stack. Repeat this step as long as stack is not empty. Return the Postfix string.
Example : Let us see how the above algorithm will be imlemented using an example. Infix String : a+b*c-d Initially the Stack is empty and our Postfix string has no characters. Now, the first character scanned is 'a'. 'a' is added to the Postfix string. The next character scanned is '+'. It being an operator, it is pushed to the stack.
Postfix String Stack AMBALA COLLEGE OF ENGINEERING AND APPLIED RESEARCHDEVSTHALI(AMBALA)

LABORATORY MANUAL
ACE

LABORATORY MANUAL NO. . : ACECSE-203 E
LABORATORY :
ISSUE NO. : 00
ISSUE DATE :
SEMESTER : 3rd
PAGE: 02 OF 03
25
Next character scanned is 'b' which will be placed in the Postfix string. Next character is '*' which is an operator. Now, the top element of the stack is '+' which has lower precedence than '*', so '*' will be pushed to the stack.
Postfix String Stack The next character is 'c' which is placed in the Postfix string. Next character scanned is '-'. The topmost character in the stack is '*' which has a higher precedence than '-'. Thus '*' will be popped out from the stack and added to the Postfix string. Even now the stack is not empty. Now the topmost element of the stack is '+' which has equal priority to '-'. So pop the '+' from the stack and add it to the Postfix string. The '-' will be pushed to the stack.
Postfix String Stack Next character is 'd' which is added to Postfix string. Now all characters have been scanned so we must pop the remaining elements from the stack and add it to the Postfix string. At this stage we have only a '-' in the stack. It is popped out and added to the Postfix string. So, after all characters are scanned, this is how the stack and Postfix string will be :
Postfix String Stack AMBALA COLLEGE OF ENGINEERING AND APPLIED RESEARCHDEVSTHALI(AMBALA)

LABORATORY MANUAL
ACE

LABORATORY :
ISSUE NO. : 00
ISSUE DATE :
SEMESTER : 3rd
PAGE: 03 OF 03
End result :
Infix String : a+b*c-d

26
Postfix String : abc*+dPost Fix Expression Evaluation
.insert the Sentinel at the end of the expression. Now, start scanning from left to right, when an operand comes, push it onto the stack and when an operator(op) comes, simply pop two topmost operands from the stack (say A and B) and perform the respective operation(B op A) and push the result (B op A)back onto the stack.
ACE

LABORATORY MANUAL

LABORATORY :
ISSUE NO. : 00
ISSUE DATE :
SEMESTER : 3rd
PAGE: 01 OF 01
Aim: Implement the evaluation of Postfix Expression.

Postfix Expression evaluation Algo:
27
1. Scan the Postfix string from left to right. 2. Initialize an empty stack. 3. If the scanned character is an operand, add it to the stack. If the scanned character is an operator, there will be at least two operands in the stack. 4. If the scanned character is an Operator, then we store the top most element of the stack(topStack) in a variable temp. Pop the stack. Now evaluate topStack(Operator)temp. Let the result of this operation be retVal. Pop the stack and Push retVal into the stack. 5. Repeat this step till all the characters are scanned. 6. After all characters are scanned, we will have only one element in the stack. Return topStack as result
ACE

LABORATORY MANUAL

LABORATORY :
ISSUE NO. : 00
ISSUE DATE :
SEMESTER : 3rd
PAGE: 01 OF 04
Aim: Implement linked list in data structure.

28
It is a data structure that consists of a sequence of data records such that in each record there is a field that contains a reference (i.e., a link) to the next record in the sequence.
A linked list whose nodes contain two fields: an integer value and a link to the next node
Linked lists are among the simplest and most common data structures, and are used to implement many important abstract data structures, such as stacks, queues, hash tables, symbolic expressions, skip lists, and many more. The principal benefit of a linked list over a conventional array is that the order of the linked items may be different from the order that the data items are stored in memory or on disk. For that reason, linked lists allow insertion and removal of nodes at any point in the list, with a constant number of operations. On the other hand, linked lists by themselves do not allow random access to the data, or any form of efficient indexing. Thus, many basic operations such as obtaining the last node of the list, or finding a node that contains a given datum, or locating the place where a new node should be inserted may require scanning most of the list elements. Linked lists can be implemented in most languages. Languages such as Lisp and Scheme have the data structure built in, along with operations to access the linked list. Procedural or objectoriented languages such as C, C++, and Java typically rely on mutable references to create linked lists. Basic concepts Each record of a linked list is often called an element or node. The field of each node that contains the address of the next node is usually called the next link or next pointer. The remaining fields are known as the data, information, value, or payload fields. The head of a list is its first node, and the tail is the list minus that node (or a pointer thereto). Linear and circular lists In the last node of a list, the link field often contains a null reference, a special value that is interpreted by programs as meaning "there is no such node". A less common convention is to make it point to the first node of the list; in that case the list is said to be circular or circularly linked; otherwise it is said to be open or linear. AMBALA COLLEGE OF ENGINEERING AND APPLIED RESEARCHDEVSTHALI(AMBALA)
LABORATORY MANUAL
ACE

LABORATORY :
ISSUE NO. : 00
ISSUE DATE :
SEMESTER : 3rd
PAGE: 02 OF 04
29
Singly-, doubly-, and multiply-linked lists Singly-linked lists contain nodes which have a data field as well as a next field, which points to the next node in the linked list.
A singly-linked list whose nodes contain two fields: an integer value and a link to the next node In a doubly-linked list, each node contains, besides the next-node link, a second link field pointing to the previous node in the sequence. The two links may be called forward(s) and backwards.
A doubly-linked list whose nodes contain three fields: an integer value, the link forward to the next node, and the link backward to the previous node The technique known as XOR-linking allows a doubly-linked list to be implemented using a single link field in each node. However, this technique requires the ability to do bit operations on addresses, and therefore may not be available in some high-level languages. In a multiply-linked list, each node contains two or more link fields, each field being used to connect the same set of data records in a different order (e.g., by name, by department, by date of birth, etc.). (While doubly-linked lists can be seen as special cases of multiply-linked list, the fact that the two orders are opposite to each other leads to simpler and more efficient algorithms, so they are usually treated as a separate case.) LINKED LIST OPERATIONS: Traversal of a singly-linked list is simple, beginning at the first node and following each next link until we come to the end:
node := list.firstNode while node not null { (do something with node.data) node := node.next } AMBALA COLLEGE OF ENGINEERING AND APPLIED RESEARCHACE DEVSTHALI(AMBALA)
LABORATORY MANUAL

ISSUE NO. : 00
ISSUE DATE :
30
LABORATORY : SEMESTER : 3rd
PAGE: 03 OF 04
The following code inserts a node after an existing node in a singly linked list. The diagram shows how it works. Inserting a node before an existing one cannot be done; instead, you have to locate it while keeping track of the previous node.
function insertAfter(Node node, Node newNode) { // insert newNode after node newNode.next := node.next node.next := newNode } Inserting at the beginning of the list requires a separate function. This requires updating firstNode. function insertBeginning(List list, Node newNode) { // insert node before current first node newNode.next := list.firstNode list.firstNode := newNode } Similarly, we have functions for removing the node after a given node, and for removing a node from the beginning of the list. The diagram demonstrates the former. To find and remove a particular node, one must again keep track of the previous element.
function removeAfter(node node) { // remove node past this one obsoleteNode := node.next node.next := node.next.next destroy obsoleteNode AMBALA COLLEGE OF ENGINEERING AND APPLIED RESEARCHACE DEVSTHALI(AMBALA)
LABORATORY MANUAL

ISSUE NO. : 00
ISSUE DATE :
31
PAGE: 04 OF 04
function removeBeginning(List list) { // remove first node obsoleteNode := list.firstNode list.firstNode := list.firstNode.next // point past deleted node destroy obsoleteNode } .
ACE

LABORATORY MANUAL

ISSUE NO. : 00
ISSUE DATE :
32
PAGE: 01 OF 01
Aim: Implement circular linked list.

Both types of circularly-linked lists benefit from the ability to traverse the full list beginning at any given node. This often allows us to avoid storing firstNode and lastNode, although if the list may be empty we need a special representation for the empty list, such as a lastNode variable which points to some node in the list or is null if it's empty; we use such a lastNode here. This representation significantly simplifies adding and removing nodes with a non-empty list, but empty lists are then a special case. Algorithms Assuming that someNode is some node in a non-empty circular singly-linked list, this code iterates through that list starting with someNode: function iterate(someNode) if someNode null node := someNode do do something with node.value node := node.next while node someNode Notice that the test "while node someNode" must be at the end of the loop. If it were replaced by the test "" at the beginning of the loop, the procedure would fail whenever the list had only one node. This function inserts a node "newNode" into a circular linked list after a given node "node". If "node" is null, it assumes that the list is empty. function insertAfter(Node node, Node newNode) if node = null newNode.next := newNode else newNode.next := node.next node.next := newNode Suppose that "L" is a variable pointing to the last node of a circular linked list (or null if the list is empty). To append "newNode" to the end of the list, one may do insertAfter(L, newNode) L = newNode To insert "newNode" at the beginning of the list, one may do insertAfter(L, newNode) if L = null
ACE
LABORATORY MANUAL

33
EXPERIMENT TITLE :
LABORATORT MANUAL NO. . : ACE- CSE-203 E

LABORATORY :
ISSUE NO. : 00
SEMESTER :

Ds Lab Manual

Uploaded by

Copyright:

Available Formats

Ds Lab Manual

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Ds Lab Manual

Uploaded by

Copyright:

Available Formats

2

AMBALA COLLEGE OF ENGINEERING AND APPLIED RESEARCHDEVSTHALI(AMBALA)

PRACTICAL EXPERIMENT INSTRUCTION SHEET

MASTER LIST OF EXPERIMENT

PREPARED BY:ER.RAJEEV GOEL

AMBALA COLLEGE OF ENGINEERING AND APPLIED RESEARCHDEVSTHALI(AMBALA)

PRACTICAL EXPERIMENT INSTRUCTION SHEET

PREPARED BY:ER.RAJEEV GOEL

APPROVED BY: Prof. ARVIND SELWAL

AMBALA COLLEGE OF ENGINEERING AND APPLIED RESEARCHDEVSTHALI(AMBALA)

PRACTICAL EXPERIMENT INSTRUCTION SHEET

Aim: Implement BUBBLE SORT algorithm on a given array of numbers.

PREPARED BY:ER.RAJEEV GOEL

APPROVED BY: Prof. ARVIND SELWAL

AMBALA COLLEGE OF ENGINEERING AND APPLIED RESEARCHDEVSTHALI(AMBALA)

PRACTICAL EXPERIMENT INSTRUCTION SHEET

end procedure FLOWCHART

PREPARED BY:ER.RAJEEV GOEL

APPROVED BY: Prof. ARVIND SELWAL

AMBALA COLLEGE OF ENGINEERING AND APPLIED RESEARCHDEVSTHALI(AMBALA)

PRACTICAL EXPERIMENT INSTRUCTION SHEET

Aim: Implement SELECTION SORT algorithm on a given array of numbers.

data[min] = temp; } AMBALA COLLEGE OF ENGINEERING AND APPLIED RESEARCHACE DEVSTHALI(AMBALA)

PRACTICAL EXPERIMENT INSTRUCTION SHEET

PREPARED BY:ER.RAJEEV GOEL

APPROVED BY: Prof. ARVIND SELWAL

AMBALA COLLEGE OF ENGINEERING AND APPLIED RESEARCHDEVSTHALI(AMBALA)

PRACTICAL EXPERIMENT INSTRUCTION SHEET

O(n2) O(n) O(n2) O(1) auxiliary

PREPARED BY:ER.RAJEEV GOEL

APPROVED BY: Prof. ARVIND SELWAL

AMBALA COLLEGE OF ENGINEERING AND APPLIED RESEARCHDEVSTHALI(AMBALA)

PRACTICAL EXPERIMENT INSTRUCTION SHEET

Aim: Implement INSERTION SORT algorithm on a given array of numbers.

AMBALA COLLEGE OF ENGINEERING AND APPLIED RESEARCHDEVSTHALI(AMBALA)

PRACTICAL EXPERIMENT INSTRUCTION SHEET

O(n2) O(n) O(n2) O(1) auxiliary

PREPARED BY:ER.RAJEEV GOEL

APPROVED BY: Prof. ARVIND SELWAL

AMBALA COLLEGE OF ENGINEERING AND APPLIED RESEARCHDEVSTHALI(AMBALA)

PRACTICAL EXPERIMENT INSTRUCTION SHEET

Aim: Implement QUICK SORT algorithm on a given array of numbers..

if array[i] pivotValue AMBALA COLLEGE OF ENGINEERING AND APPLIED RESEARCHDEVSTHALI(AMBALA)

PRACTICAL EXPERIMENT INSTRUCTION SHEET

PREPARED BY:ER.RAJEEV GOEL

APPROVED BY: Prof. ARVIND SELWAL

AMBALA COLLEGE OF ENGINEERING AND APPLIED RESEARCHDEVSTHALI(AMBALA)

PRACTICAL EXPERIMENT INSTRUCTION SHEET

Aim: Implement LINEAR SEARCH algorithm on a given array of numbers.

Figure %: Is the third value 3? Not there either. Next

PREPARED BY:ER.RAJEEV GOEL

APPROVED BY: Prof. ARVIND SELWAL

AMBALA COLLEGE OF ENGINEERING AND APPLIED RESEARCHDEVSTHALI(AMBALA)

PRACTICAL EXPERIMENT INSTRUCTION SHEET

PREPARED BY:ER.RAJEEV GOEL

APPROVED BY: Prof. ARVIND SELWAL

AMBALA COLLEGE OF ENGINEERING AND APPLIED RESEARCHDEVSTHALI(AMBALA)

PRACTICAL EXPERIMENT INSTRUCTION SHEET

Aim: Implement BINARY SEARCH algorithm on a given array of numbers

PREPARED BY:ER.RAJEEV GOEL