DATA STRUCTURE AND ALGORITHM

CHAPTER 3

List
Data Structures
DATA STRUCTURE AND ALGORITHM 1
CONTENTS

 List ADT
 Array implementation of List ADT,
 Operations
 Time and space complexity of array implementation

 Linked list:-
 Singly linked lists,
 doubly linked lists,
 circular (singly and doubly) linked lists,

 Operations on linked lists:

 creation, insertion, deletion, update, search

DATA STRUCTURE AND ALGORITHM 2

LIST ADT
 A list contains elements of same type arranged in sequential order.
 Lists are very common in computing
 e.g. student list, list of events, list of appointments etc

 Two Major Implementations

 Array implementation
 Linked list implementation

DATA STRUCTURE AND ALGORITHM 3

ARRAY IMPLEMENTATION OF LIST ADT

 Array is a list of a finite number n of homogeneous data elements

 The elements of the array are stored respectively in successive memory locations.

 Array is a prime candidate for implementing list ADT

 Simple construct to handle a collection of items

 Operations

 addAt(), removeAt(), getSize(), isEmpty()…etc.

 Advantage:

 Very fast retrieval

DATA STRUCTURE AND ALGORITHM 4

INSERTION : USING ARRAY
 Simplest Case: Insert to the end of array
 Other Insertions:
 Some items in the list needs to be shifted
 Worst case: Inserting at the head of array

DATA STRUCTURE AND ALGORITHM 5

DELETION: USING ARRAY
 Simplest Case: Delete item from the end of array
 Other deletions:
 Items needs to be shifted
 Worst Case: Deleting at the head of array

DATA STRUCTURE AND ALGORITHM 6

ARRAY IMPLEMENTATION: EFFICIENCY (TIME)

 Retrieval:

 Fast: one access

 Insertion:

 Best case: No shifting of elements

 Worst case: Shifting of all N elements.

 Deletion:

 Best case: No shifting of elements

 Worst case: Shifting of all N elements

DATA STRUCTURE AND ALGORITHM 7

ARRAY IMPLEMENTATION : EFFICIENCY (SPACE)

 Size of array is restricted to MAX_LIST

 Problem:
 Maximum size is not known in advance

 Solution:
 Make MAX_LIST a variable
 When array is full:

1. Create a larger array

2. Move the elements from the old array to the new array
 No more limits on size, but space wastage and copying overhead is still a problem
 MAX_LIST is too big == unused space is wasted
 MAX_LIST is too small == run out of space easily

DATA STRUCTURE AND ALGORITHM 8

ARRAY IMPLEMENTATION : SUMMARY

 For fixed-size collections

 Arrays are great

 For variable-size collections, where dynamic operations such as insert/delete are common
 Array is a poor choice of data structure

 For such applications, there is a better way……

 Limitation of Array
 Changing the size of the array requires creating a new array

 Inserting/deleting an item requires shifting

DATA STRUCTURE AND ALGORITHM 9

LINKED LIST

 A linked list consists of a finite sequence of elements or nodes (not necessarily adjacent in memory) that contain

information plus (except possibly the last one) a link to another node.

 Unlike an array, however, in which the linear order is determined by the array indices, the order in a linked list is

determined by a pointer in each object.

 If node x points to node y, then x is called the predecessor of y and y the successor of x.

 There is a link to the first element called the head of the list.

 Linked lists provide a simple, flexible representation for dynamic sets.

 is used quite frequently since it is very efficient.

DATA STRUCTURE AND ALGORITHM 10

CONT..

 As elements are added to a list, memory for a node is dynamically allocated.

 Therefore, the number of elements that may be added to a list is limited only by the amount of memory available.

 A linked list can be implemented using struct Node {

int data;
 arrays,
Node* next;
 dynamic memory management, and pointers. };

 The second implementation requires dynamic memory management where one can allocate memory at run-time, that is, during

the execution of a program.

 Linked lists are generally implemented using dynamic memory management. Node *head = new Node;

DATA STRUCTURE AND ALGORITHM 11

SINGLY LINKED LIST

 A linked list is an ordered collection of data in which each element (node) contains a minimum of two values,
 data and link(s) to its successor (and/or predecessor).

 If a node has a link only to its successor in this sequence, the list is called a singly linked list.
 Each node of the linked list has at least the following two elements:

1. The data member(s) being stored in the list.

2. A pointer or link to the next element in the list.

Head

 The last node in the list contains a null pointer (or a suitable value like -1) to indicate that it is the end or tail of the list

DATA STRUCTURE AND ALGORITHM 12

DOUBLY LINKED LIST
 In SLL, each node provides information about where the next node is.
 It has no knowledge about where the previous node is.

 For handling such difficulties, we can use DLLs where each node contains two links,
 one to its predecessor and other to its successor

 Each node of a DLL has three fields in general but must have at least two link fields

DATA STRUCTURE AND ALGORITHM 13

CIRCULAR SINGLY LINKED LIST

 So far we have seen linear linked lists, Has some drawbacks

 In SLL, we cannot reach any of the nodes that precede the Current node

 The above problem is not the case in DLL but the problem can be solved by….

 In a SLL, the last nodes link field is set to Null.

 Instead of that, store the address of the first node of the list in that link field.

 Such a linked list is called Circular Singly Linked List

DATA STRUCTURE AND ALGORITHM 14

CIRCULAR DOUBLY LINKED LIST

 In doubly circular linked list,

 the last node’s next link is set to the first node of the list and

 the first node’s previous link is set to the last node of the list.

 This gives access to the last node directly from the first node

DATA STRUCTURE AND ALGORITHM 15

LINKED LIST OPERATIONS

The following are basic operations associated with the linked list as a data structure:

 Creating an empty list

 Inserting a node

 Deleting a node

 Traversing the list

 Some more operations, which are based on the basic operations, are as follows:

 Searching a node, Updating a node, Printing the node or list, Counting the length of the list, Reversing the list, Sorting the list

using pointer manipulation, Concatenating two lists, Merging two sorted lists into a third sorted list

DATA STRUCTURE AND ALGORITHM 16

INSERTION ALGORITHM VS C++ IMPLEMENTATION

void insertFront(struct Node **head, int n) {

Insert-Front(Node head, x)
Node *newNode = new Node;
1. Create newNode
newNode->data = n;
2. newNode.data <- x
newNode->next = *head;
3. newNode.next <- head
*head = newNode;
4. head <- newNode
}

DATA STRUCTURE AND ALGORITHM 17

 BASIC OPERATIONS – INSERTION AT THE BEGINNING OF THE
LIST

Head
56 12 70 8

Head
5 56 12 70 8

Head
5 56 12 70 8

Head
5 56 12 70 8

DATA STRUCTURE AND ALGORITHM 18

TRAVERSING THE LINKED LIST

56 12 70 8

TRAVERSE-LIST(Node head) void TRAVERSE_LIST(struct Node *head) {

1 cur ← head Node *list = head;
2 while cur != Null while(list) {
3 do Disp cur.data cout << list->data << " ";
4 cur ← cur.next list = list->next;
}
}

DATA STRUCTURE AND ALGORITHM 19

INSERTION ALGORITHM VS C++ IMPLEMENTATION

InsertAtEnd(Node head, x)
1. Create newNode
2. newNode.data <- x
3. cur <- head
4. while cur != Null
5. do
6. if cur.next = Null
7. cur.next <- newNode
8. return
9. cur ← cur.next
DATA STRUCTURE AND ALGORITHM 20
BASIC OPERATIONS – INSERTION AT THE END OF THE LIST

Head
56 12 70 8

Head
56 12 70 8 5

Head
56 12 70 8 5

Head
56 12 70 8 5

DATA STRUCTURE AND ALGORITHM 21

BASIC OPERATIONS – INSERTION AT THE MIDDLE OF THE LIST
5
Head
56 12 70 8

5
Head
56 12 70 8

5
Head
56 12 70 8

5
Head
DATA STRUCTURE AND ALGORITHM
56 12 70 8 22
BASIC OPERATIONS – DELETION AT THE BEGINNING OF THE
LIST

Head
56 12 70 8

Head
56 12 70 8

Head
56 12 70 8

Head
12 70 8

DATA STRUCTURE AND ALGORITHM 23

BASIC OPERATIONS – DELETION AT THE BEGINNING OF THE
LIST

DATA STRUCTURE AND ALGORITHM 24

BASIC OPERATIONS – DELETION AT THE MIDDLE OF THE LIST

Head
56 12 70 8

Head
56 12 70 8

Head
56 12 70 8

Head
56 70 8

DATA STRUCTURE AND ALGORITHM 25

BASIC OPERATIONS – DELETION AT THE MIDDLE OF THE LIST

DATA STRUCTURE AND ALGORITHM 26

BASIC OPERATIONS – DELETION AT THE END OF THE LIST

Head
56 12 70 8

Head
56 12 70 8

Head
56 12 70 8

Head
56 12 70

DATA STRUCTURE AND ALGORITHM 27

SEARCH OPERATION IN LINKED LIST

struct Node *searchNode(struct Node *head, int n) {

SEARCH-LIST(head, key)
Node *cur = head;
1 cur ← head
while(cur) {
2 while cur != Null
if(cur->data == n) return cur;
3 do if cur.data = key
cur = cur->next;
4 return cur
}
5 cur ← cur.next
return null;
6 Return null
}
DATA STRUCTURE AND ALGORITHM 28
ADVANTAGES OF LINKED LIST OVER ARRAY

Advantages
 1) Dynamic size
 2) Ease of insertion/deletion

Drawbacks:
 1) Random access is not allowed. We have to access elements sequentially starting from the first node.
 2) Extra memory space for a pointer is required with each element of the list.
 3) Not cache friendly. Since array elements are contiguous locations, there is locality of reference which is not
there in case of linked lists.

DATA STRUCTURE AND ALGORITHM 29

COMPARISON OF SEQUENTIAL AND LINKED ORGANIZATIONS

Sequential organization The features of this organization are the following:

1. Successive elements of a list are stored a fixed distance apart.

2. It provides static allocation, which means, the space allocation done by a compiler once cannot be changed during execution,
and the size has to be known in advance.

3. As individual objects are stored a fixed distance apart, we can access any element randomly.

4. Insertion and deletion of objects in between the list require a lot of data movement.

5. It is space inefficient for large objects with frequent insertions and deletions.

6. An element need not know/store and keep the address of its successive element.

DATA STRUCTURE AND ALGORITHM 30

COMPARISON OF SEQUENTIAL AND LINKED ORGANIZATIONS
Linked organization The features of this organization include the following:
1. Elements can be placed anywhere in the memory.
2. Dynamic allocation (size need not be known in advance), that is, space allocation as per need can be done during
execution.
3. As objects are not placed in consecutive locations at a fixed distance apart, random access to elements is not possible.
4. Insertion and deletion of objects do not require any data shifting.
5. It is space efficient for large objects with frequent insertions and deletions.
6. Each element in general is a collection of data and a link. At least one link field is a must.
7. Every element keeps the address of its successor element in a link field.
8. The only burden is that we need additional space for the link field for each element. However, additional space is not a
severe penalty when large objects are to be stored.
9. Linked organization needs the use of pointers and dynamic memory allocation.
DATA STRUCTURE AND ALGORITHM 31
QUIZ 1

Write an algorithm for program that

returns the number of the nodes in the
linked list?

DATA STRUCTURE AND ALGORITHM 32

QUIZ 1

Write an algorithm for program that

update the a value of a node in a linked
list?
 Note: the node can be located anywhere in the linked list.

DATA STRUCTURE AND ALGORITHM 33