Teachers: structure

Showing posts with label structure. Show all posts

Wednesday, February 18, 2015

Skip List Data Structure

A skip list is a data structure that is used for storing a sorted list of items with a help of hierarchy of linked lists that connect increasingly sparse subsequences of the items. A skip list allows the process of item look up in efficient manner. The skip list data structure skips over many of the items of the full list in one step, that’s why it is known as skip list.

Skip List

Complexity

	Average Case	Worst Case
Space	O(n)	O(nlogn)
Search	O(logn)	O(n)
Insert	O(logn)	O(n)
Delete	O(logn)	O(n)

Structure of Skip List

A skip list is built up of layers. The lowest layer (i.e. bottom layer) is an ordinary ordered linked list. The higher layers are like ‘express lane’ where the nodes are skipped (observe the figure).

Searching Process

When an element is tried to search, the search begins at the head element of the top list. It proceeds horizontally until the current element is greater than or equal to the target. If current element and target are matched, it means they are equal and search gets finished.

If the current element is greater than target, the search goes on and reaches to the end of the linked list, the procedure is repeated after returning to the previous element and the search reaches to the next lower list (vertically).

Implementation Details

1. The elements used for a skip list can contain more than one pointers since they are allowed to participated in more than one list.

2. Insertion and deletion operations are very similar to corresponding linked list operations.

Insertion in Skip List

Applications of Skip List

1. Skip list are used in distributed applications. In distributed systems, the nodes of skip list represents the computer systems and pointers represent network connection.

2. Skip list are used for implementing highly scalable concurrent priority queues with less lock contention (struggle for having a lock on a data item).

Explain Basic Structure of C Programs

Documentation Section

This section consists of comment lines which include the name of programmer, the author and other details like time and date of writing the program. Documentation section helps anyone to get an overview of the program.

Link Section

The link section consists of the header files of the functions that are used in the program. It provides instructions to the complier to link functions from the system library.

Also Read: List of all useful Turbo C++ keyboard shortcuts
Also Read: How to create your own Header Files in C/C++?

Definition Section

All the symbolic constants are written in definition section. Macros are known as symbolic constants.

Global Declaration Section

The global variables that can be used anywhere in the program are declared in global declaration section. This section also declares the user defined functions.

main() Function Section

It is necessary have one main() function section in every C program. This section contains two parts, declaration and executable part. The declaration part declares all the variables that are used in executable part. These two parts must be written in between the opening and closing braces. Each statement in the declaration and executable part must end with a semicolon (;). The execution of program starts at opening braces and ends at closing braces.

Also Read: What are advantages and disadvantages of C language?
Also Read: How to Write and Run C/C++ Programs in Ubuntu (Linux)

Subprogram Section

The subprogram section contains all the user defined functions that are used to perform a specific task. These user defined functions are called in the main() function.

What is Disjoint set Data Structure

It is a data structure to keep a record of set of elements that are partitioned into number of disjoint subsets.

Such type of data structure performs three basic operations:

1. MakeSet operation
2. Find operation
3. Union operation

Sometimes, it is called Union-Find data structure or Merge-Find data structure.

Applications

It is used as an auxiliary data structure for various algorithms like Kruskal’s algorithm in graph theory and other partitioning problems.

Also Read: C Program for Tower of Hanoi Problem
Also Read: C Program for Sorting an Array using Heap Sort

MakeSet Operation

Initially, input elements are considered as a collection of n sets, of which each element in each set. Each set has different element, so S_i ∩ S_j= Φ. This makes sets disjoints.

The operation MakeSet creates a new set containing a single element for each given element. MakeSet creates a set of singleton elements in which each element represent its own set as shown below.

Union and Find Operation

To add relation, aRb (a and b can be any element from given elements) we use Union operation. But to do union we have to find out that whether a and b are related or not.

This can be verified by Find operation. Find operation check whether a and b are already related or not. If they are not, then union is applied creating a new set S_k = S_iU S_j and deletes S_iand S_j. If they are related, Find returns the set in which they are located.

Eg: After some operations of union, some sets are grouped together as shown below:

What is Disjoint-set Data Structure (Union and Find Operation)?

To represent each set, which is important, an element is fixed which is called representative of that set. So, while we are using Find operation on any element X, it will return the representative of the set in which element X is present.

For better understanding watch below video:

In next tutorial we will be discussing about implementations of disjoint-set data structure.

Author Bio:
Manisha Khandelwal is a computer science engineering student who lives in India. Data Structure is one of her favorite subjects. You can find her on Facebook at http://www.facebook.com/mannkhandelwal or contact her on Gmail at manishakhandelwal2611@gmail.com.

Teachers