Home Classroom Algorithms Basics of Algorithms Part 4

Basics of Algorithms Part 4

1208

1. Introduction

A data structure is basically what it is. It is a structure of data. However, every data structure has a particular way of storing data, and data is retrieved / manipulated using certain operations which are defined for that data structure. The efficiency of these operations decide on the suitability of a data structure for a particular purpose.

 

2. Linked List

A linked list is a data structure which consists of a sequence of elements. Each element contains data and a link. The link is used to link with the next element in the record. The links are maintained with the use of pointers. The first element in the list is known as the head, and the pointer to the head is stored to perform operations on the linked list.

As we can see, the elements are linked together. The last link is a ‘Null’ pointer, signifying the end of the list. Since we only have the head pointer with us, we can not move to any random element in the list directly, we need to start from the head pointer and sequentially move to the next element, until we arrive at the desired element. This is known as traversing a list.

The most important operations on a Linked List are:

a) Insert: Insert an element in the beginning / middle / end of the list. Insertion at the beginning is O(1). If the pointer to the last element is stored, insertion at the end can be done in O(1). Since to insert in the middle, we would need to traverse the list, and if there are n elements in the list, the insertion is O(n).

b) Delete: Delete an element from the beginning / middle / end of the list. Deletion of elements have the same complexity as insertion.

 

Other types of Linked List:

a) Doubly Linked List:
A normal linked list has a link only to the next element. In a doubly linked list, each element has a link to the next and previous element.

This type of linked list allows traversal in both directions.

b) Circular Linked List:
In a circular linked list, the last element links to the head of the linked list. Thus, the next element after the last element, is actually the first one in the list.

struct node {
element e;
node *next;
};

node * head;

void insert_in_front(node * n) {
if(head == NULL)
{ head = n; head->next = NULL; return; }

n->next = head;
head = n;
}

void delete_in_front() {
if(head == NULL) {
cout << “Cannot delete”; return;

}
node * ret = head;
head = head->next;
free(ret); //If memory was allocated using malloc
}
element is a user-defined data-type. You can use templates to make it generic.

 

2. Stack

A stack is a data structure, in which elements are added to and removed from the ‘top’ of the stack. We can only access the element at the top of the stack. A stack can be maintained using a linked list with two restrictions as mentioned above, i.e. insertion and deletion happens only at the front of the list. A stack can also be implemented using an array.

 

The two operations involved in a stack are:

a) Push: Adding an element to the top of a stack is known as pushing an element. Pushing an element is an O(1) operation. If number of elements in a stack exceeds the desired limit, (or if it runs out of space if implemented using an array) it is known as a stack overflow error.

b) Pop: Removing an element to the top of a stack is known as popping an element. Popping the element is an O(1) operation. If an element cannot be popped, it is known as a stack underflow error.

c) Peek: This operation returns the element at the stack top. This is also an O(1) operation.

struct Stack {
int stack_top;
element stack[MAXSIZE]; };
void stack_init(Stack &s) {
s.stack_top = -1;
}
int stack_push(Stack &s, element e) {
if(s.stack_top == MAXSIZE) {
cout << “Stack Overflow”;
return -1;
}
s.stack[s.stack_top++] = e;
return 1;
}
int stack_pop(Stack &s, element &e) {
if(s.stack_top == -1) {
cout << “Stack Underflow”; return -1;
}
e = s.stack[s.stack_top--];
return 1;
}
int stack_peek(Stack &s, element &e) {
if(s.stack_top == -1) {
cout << “Empty stack”; return -1;
}
e = s.stack[s.stack_top];
return 1;
}

 

4. Tasks for you:
  1. Complete the code for Linked List to include insertion and deletion in middle and at rear.
  2. Extend the Linked List functions for Doubly Linked List and Circular Linked List.
  3. Study the Josephus’ problem and solve it using Circular Linked Lists.
  4. Using stacks, find the reverse of a string.
  5. A stack is used to check if parentheses are well-formed. For eg. “(())” and “()(())” are well-formed parentheses, but “((()” is not. Given a string, find if a string is a well-formed paretheses string using stacks.

Comments

comments

Gaurav is a final year student of Computer Engineering at Thadomal Shahani Engineering College, University of Mumbai (India). His handle on TopCoder is ‘red.dragon’.His areas of interest are Algorithms, Grid Computing and Cryptography

NO COMMENTS

Leave a Reply