Data structure and algorithms

Page 1

Introduction to data structure:

A data structure is a way to store and organize data in a computer, so that it can be use efficiently.

two ways to represent data structure:

1. Mathematical / logical models: the abstract vi any model. (abstract data type (ADT), e.g.: array linked list))

ADT: define data and operation, but no implementations.

E.G.: array, linked list, stack, queue, tree, graph.

Logical view

Operations

Cost of operations (mainly in terms of time)

Implementations

List as abstract data type:

a static list that can:

store a given number of elements of a given data type.

write/modify element.

read element at a position.

this is basically an array.

A dynamic list that:

empty list has size 0

insert

remove

count

read / modify element at a position.

specify the data type.

let's say we have array of maximum size: int A[maximum size], if the list is empty the, a variable that specifies the end index of the end element will be -1, i.e.,

int end =-1.

if we want to insert a number 2 in the list, it will always insert the element at the tail or at the end of the list. if we want to insert an element at a fixed position, then the element from that position will be shifted one unit at a time.

likewise, if we want to remove any element from a list, then the elements after the same will move a unit to left.

a list can grow to exhaust an array, when this happens, we can create a new and larger array and copy the elements into the larger array (i.e., double the size of the existing array) and free the memory for the previous array.

Cost of implementation of these process in terms of time will be:

access-read/ write element at an index will take constant time, the time complexity is written as, O(1).

insert (at a specified position)-will be proportional to the length of the list (length of n), O(n).

remove-will also be proportional to the length of the list(n), O(n).

inserting an element (when a list is full)-proportional to the length of the new array, O(n).

we conclude that it is easier to access any element, but it is costly when inserting or remove any element, also a lot of time, a lot of array is unused that is a lot of memory is unused, hence it is not efficient in terms of memory. this is where linked list comes in.

Page 2

Intoduction to Linked list:

When storng some ellment, it acquries a specifc amount of menory, like in cse of integer data type it take about 4 bits. but soring of this eement is not e after another it is actually strayed alg the memoy, i.e. it can be stroed in any place. so we cn use list as an array but using it has many isadvantages so the best way is to sve the elements as a single unit andd the linking them together, this way we can save time as well a lot of memory.the way is called as linked list.

to specify the next data, address is used. node s used that can store two variables, one for the data and the second for the address of the scond node.