Double Linked list is a fundamental data structure used in computer programming. It consists of a sequence of nodes connected by two pointers in both directions. Each node is having three parts the first part contains the address of previous node and second part contains data and third part contains address of next node. The first and third part is called address fields and the second part is data field.
Thursday, December 6, 2007
Single Linked List
Single Linked list is a linear data structure. It is used as a fundamental data structure in computer programming. It contains a collection of nodes which are connected by only one pointer in one direction. Each node is having two parts the first part contains the data and second part contains the address of the next node. The first part is called data field or information field and the second part is called as link field or next address field.
The graphical representation of linked list is
Hear the pointer start always points to the first node of a list and the end node is represented by special value called NULL.
Linked Lists
Linked list: -
Linked list is a linear data structure that works on a principle Random in Random out (RIRO). Linked list can be defined as Collection of logically adjacent nodes in which logical adjacency is maintained by pointers.
Ex: The days of the week (Sun, Mon, Tue, Wed, Thu, Fri, Sat)
Linked lists can be represented in memory by two ways they are
· Using array method 2. Using pointer method
Circular Queue Data Structure
In a standard queue data structure re-buffering problem occurs for each dequeue operation. To solve this problem by joining the front and rear ends of a queue to make the queue as a circular queue
Circular queue is a linear data structure. It follows FIFO principle.
- In circular queue the last node is connected back to the first node to make a circle.
- Circular linked list fallow the First In First Out principle
- Elements are added at the rear end and the elements are deleted at front end of the queue
- Both the front and the rear pointers points to the beginning of the array.
- It is also called as “Ring buffer”.
- Items can inserted and deleted from a queue in O(1) time.
DeQueue Data Structure
DeQueue (or) Deque (Double ended Queue) :-
DeQueue is a data structure in which elements may be added to or deleted from the front or the rear.
Like an ordinary queue, a double-ended queue is a data structure it supports the following operations: enq_front, enq_back, deq_front, deq_back, and empty. Dequeue can be behave like a queue by using only enq_front and deq_front , and behaves like a stack by using only enq_front and deq_rear. .
The DeQueue is represented as follows.
Priority Queue
Priority queue is a linear data structure. It is having a list of items in which each item has associated priority. It works on a principle add an element to the queue with an associated priority and remove the element from the queue that has the highest priority. In general different items may have different priorities.
Wednesday, December 5, 2007
Queue Data Structure
- Queue is a linear data structure
- it works on the principle First In First Out (FIFO).
- The first element insert into the queue is the first element to be delete
- Insertion can be done at rear end using rear pointer and deletions can be done at front end using front pointer
- It looks like open tube.
Applications of Stack Data Structure
The linear data structure stack can be used in the following situations.
1. It can be used to process function calls.
2. Implementing recursive functions in high level languages
3. Converting and evaluating expressions.
Classification of Data structures
Data structures can be classified as
· Simple data structure
· Compound data structure
· Linear data structure
· Non linear data structure
Data Structure Definitions
In computer science, a data structure is a way of storing data in a computer so that it can be used efficiently. Often a carefully chosen data structure will allow the most efficient algorithm to be used. The choice of the data structure often begins from the choice of an abstract data type. A well-designed data structure allows a variety of critical operations to be performed, using as few resources, both execution time and memory space, as possible. Data structures are implemented by a programming language as data types and the references and operations they provide.
Subscribe to:
Posts (Atom)
