Definition of List and Linked List

List is a generic term for a collection of objects. It may or may not contain duplicates and application may or may not require that it be kept in specified order.

The functions defined to operate on a list are

·         Insert:  Insert a new entry into a list
·         Delete: Delete an entry from list
·         Length: Compute length of a list
·         Next: Return the next element in a list
·         Search: Search if an element is in a list

Linear list: A linear list is a sequence of n>=0 nodes x[1], x[2], x[3] ……………x[n] whose essential structural properties between items as they appear in a line.

Restricted list: In restricted list, Data can only be added or deleted at the ends of a structure and processing is restricted to operations at the end of lists.

The two restricted list structures are First In First Out (FIFO) stacks and Last In First Out (LIFO) queue.

The four operations performed on linear lists are

         i.            Insertion
       ii.            Deletion
      iii.            Retrieval
     iv.            Traversal

         Depending on the type of linear list, an insertion can be made at the beginning of the list, or at the end of the lists. When inserting data into ordered list, the data must be inserted so that the ordering is maintained. Deletion from general lists requires that the list be searched for the data to be deleted.

List retrieval requires that data be located in a list and presented to the calling module without changing the contents of the lists.

List traversal is a special case of retrieval in which all the elements are retrieved in a sequence.

Definition of Linked list

A link list is a collection of records, called nodes, each containing at least one field(member) that gives the location of the next node contains two members; a data member (the value of the list item) and a link member (a value locating the next node).The link list is a very flexible dynamic data structure. It is a low-level structure upon which high-level data structures can be built.

The Typical basic linked-list operations are

         i.            Create: Makes a new linked list
       ii.            Insert: Puts a new node in its place in the list.
      iii.            Remove: Remove a node from the list.
     iv.            Traverse: This function allow user to visit each node in the list.
       v.            Is empty: The function returns a true/false indication of whether or not there are any nodes in the list.
     vi.            Is full: This function returns a true/false indication of whether or not the list is full

Types of linked lists

         i.            Singly linked lists
       ii.            Circular singly linked lists
      iii.            Doubly linked lists
     iv.            Circular Doubly linked lists

You Might also view the following Related Posts

• Fundamental of data structures
• Definition of Stack
• Definition of Queues
• Tree
• Graph Definition

For more other Posts: Click Here

Definition of Queues

A queue is defined as a special type of data structure where elements are inserted from one end and elements are deleted from other end.

The end from where the elements are inserted is called rear end (r) and the end from where elements are deleted called front end (f). In a queue always elements are inserted from the rear end and elements are deleted from the front end.

Queue is a linear list for which all insertions are made at the end of the list; all deletions (and usually all accesses) are made at the other end. So queue is also called First in First out (FIFO) data.

Different types of queues

1. Ordinary queue
2. Double ended queue
3. Circular queue
4. Priority queue

1. Ordinary queue

 

This queue operates on the first come first serve basis. Items will be inserted from one end and they are deleted at the other end in the same order in which they are inserted. A queue can be represented by using an array by using an array as shown in the figure.


The operations that can be performed on these queues are

• Insert an item at the rear end
• Delete an item from the front end
• Display the contents of the queue

Disadvantage of Ordinary queue

In an ordinary queue, as an item is inserted, the rear end identified by r is incremented by 1. Once r reaches QUEUE_SIZE-1, we say queue is full. Note that even if some elements are deleted from queue, because the rear end identified by r is still equal to QUEUE_SIZE-1, so item cannot be inserted into the queue.

2. Double ended queue (Deque)

Another type of queue called double ended queue also called Deque. Deque is a special type of data structure in which insertions and deletions will be done either at the front end or at the rear end of the queue. The operations can be performed on Deques are

• Insert an item from front end
• Insert an item from rear end
• Delete an item from front end
• Delete and item from rear end
• Display the contents of queue

3. Circular queue

In an ordinary queue, as an item is inserted, the rear end identified by r is incremented by 1. Once r reaches QUEUE_SIZE-1, we say queue is full. Note that even if some elements are deleted from queue, because the rear end identified by r is still equal to QUEUE_SIZE-1 item cannot be inserted. But this disadvantage is overcome using circular queue. In circular queue an item can be published circularly. This can be achieved using the statement r = (r+1)%QUEUE_SIZE


The operations can be performed on circular queue are.

• Insert an item from rear end
• Delete an item from front end
• Display queue contents

4. Priority queue

Such a queue where a job is processed based on the priority is called a priority queue

Related Posts

• Fundamental of data structures
• Definition of Stack
• Definition of Queues
• Definition of List and Linked List
• Tree
• Graph Definition

Definition of Stack

Stack is defined as a special type of data structure where items are inserted from one end called top of stack and items are deleted from the same end.

          Here, the last item inserted will be on top of stack. Since deletion is done from the same end, Last item is inserted is the First item to be deleted out from the stack and so, stack is also called Last In First Out (LIFO) data structure.

The various operations that can be performed on stacks are

         i.            Insert an item into the stack
       ii.            Delete an item from the stack
      iii.            Display the contents of the stack

·  Insert or push operation: Inserting an element in the stack is called push operation. This can be achieved by first increment top by 1 and then insert an item as shown below;
                top = top+1;
                s[top] = item;
These two statements can also be written as s[++top]= item
                             
When the stack is full the value of top will be [STACK SIZE -1] and it is not possible to insert any new item in the stack. This situation is called stack overflow.

·  Delete or Pop operation: Deleting the stack called pop operation. This can be achieved by first accessing the top element s[top] and then decremented top by one as shown below.

              Item = s[top--];

Each time, the item is deleted, top is decremented and finally, when the stack is empty the top will be -1. When the stack is empty, it is not possible to delete any item and this situation is called underflow of stack.

·      Display operation: Displaying the items of the stack is called display operation.

Applications of Stack:- A stack is very useful in situations when data have to be stored and then retrieved in the reverse order. Some applications of stack are listed below.
         i.            Function calls
       ii.            Large number Arithmetic
      iii.            Evaluation of arithmetic expressions

You Might also view the following Related Posts

• Fundamental of data structures
• Definition of Queues
• Definition of List and Linked List
• Tree
• Graph Definition

For more other Posts: Click Here

Fundamental of data structures

What is data Structure?

A data Structure is the organization of data in computers memory or in a file.

Some examples of data structures are: array, stack, queue, link list, binary tree hash table, heap and graph. Data structures are often used to build databases. Typically, data structures are manipulated using various algorithms.

Based on the concept of Abstract data types (ADT), we define data structure by the following three components.

1.       Operations: Specifications of external appearance of data structure.
2.     Storage Structures: Organizations of data implemented in lower-level data structures.
3.       Algorithms: Description on how to manipulate information in the storage structures to obtain the results defined for operations.

Implementation of Data Structure

There are three levels of implementation of data structure which are:
1. The Abstract Level: The abstract (or logical) level is the specifications of the data structure the “What” but not “how”. At this level. The user or data structure designer is free think outside the bounds of anyone programming language.

2. Application Level: At the application or user level, the user is modeling real-life data in a specific context.

3.  Implementation Level: The implementation level is where the model becomes compatible, executable code.

Abstract data types

                The data structure can only be accessed with defined operations. This set of operations is called interface and abstract data type is exported by the entity. An entity with the properties just described is called an abstract data type (ADT).

Properties of an abstract data type

Abstract data type is characterized by the following Properties.
1.       It exports a type.
2.       It exports a set of operations. This set is called interface.
3.       Operations of the interface are the one and only access mechanism to the type’s data structure.
4.       Axioms and preconditions define the application domain of type.

Parts of ADT description

1.       Data: This part describes the structure of the data used in the ADT in an informal way.
2.       Operations: This part describes valid operations for this ADT; hence, it describes its interface. We use special operation constructor to describe the actions which are to be performed once an entity of this ADT is created and destructed to describe the actions which are to be performed once an entity is destroyed.

You Might also view the following Related Posts

• Definition of Stack
• Definition of Queues
• Definition of List and Linked List
• Tree
• Graph Definition

For more other Posts: Click Here

Programming Language Definition

Programming Language Definition: A sequence of instructions that a computer can interpret and execute to complete task is called computer program. The language which is used to develop a computer program is called programming language. There are two types of programming language which are procedure oriented programming language and object oriented programming language.
1.       Procedure Oriented programming:Conventional programming, using high level languages such as COBOL, FORTAN and C is commonly known as procedure oriented programming (POP). In the procedure oriented approach, the problem is viewed as a sequence of things to be done such as reading, calculating and printing. Procedure oriented programming basically consists of writing a list of instructions (or actions) for the computer to flow and organizing these instructions into groups known as functions.

Characteristics of Procedure Oriented Programming
i)        Emphasis is on doing things (algorithms)
ii)       Large Programs are divided into smaller Programs Known as functions.
iii)     Most of the functions share global data
iv)     Data move openly around the system from function to function.
v)      Functions transform data from one to another.
vi)     Employs top-down approach in program design.

Drawbacks of Procedure Oriented Programming
i)        In large program it is very difficult to identify what data is used by which function. In case we need to revise an external data structure, we also need to revise all functions that access the data. This provides an Opportunity for bugs to creep in.
ii)       With the procedural approach is that it does not model real world problems very well. This is because functions are action oriented and do not really corresponding to the elements of the problem.

2.       Object-oriented Programming: Object oriented programming treats data as a critical element in the program development and does not allow it to flow freely around the system. It ties data more closely to the functions that operate on it, and protects it from accidental modification from outside functions. OOP allows decomposition of a problem into a number of entities called objects and then builds data and functions around these objects.

Characteristics of Object-Oriented programming
i)        Emphasis is on data rather than procedure.
ii)       Programs are divided into what are known as objects.
iii)     Data structures are designed such that they characterize the objects.
iv)     Functions that operate on the data of an object are tied together on the data structure.
v)      Data is hidden and cannot be accessed by external functions.
vi)     Objects may communicate with each other through functions.
vii)   New data and functions can be easily added whenever necessary. Follows bottom up approach is program design.

Benefits of Object Oriented Programming
i)        Through inheritance we can eliminate redundant code and extend the use of existing classes.
ii)       We can build programs from the standard working modules that communicate with one another, rather than having to start writing the code from scratch. This leads to saving of development time and higher productivity.
iii)     The principle of data hiding helps the programmer to build secure programs that cannot be invaded by code in other parts of the program.

Some terms used in Object Oriented Programming

Ø  Objects: Objects are basic run-time entities in an object oriented system.
Ø  Classes: A class is a collection of objects of similar type.
Ø  Data Abstraction and Encapsulation: The wrapping up of data and functions into a single unit is known as encapsulation.
Abstraction refers to the act of representing essential features to the act of representing essential features without including the background or explanations.
Ø  Inheritance: Inheritance is the process by which objects of one class acquire the properties of objects of another class.
Ø  Polymorphism: Polymorphism is another important OOP concept. Polymorphism, a Greek term means the ability to take more than one form. The operation may exhibit different instances the behavior depends upon the types of data is the operation.
Ø  Dynamic Binding: Binding refers to the linking of a procedure call to the code to be executed in response to the call. Dynamic binding (also known as late binding) means that the code associated with a given procedure call is not known until the time of the call at run time.
Ø  Message passing: A message for an object is a request for execution of a procedure and therefore will invoke a function (procedure) in the receiving object that generates the desired result.
 

Network Reference Models (Network Architectures)

The two most important reference modes are listed below

i) The OSI reference model and

ii) The TCP/IP reference model




i)        The OSI reference model

An ISO standard that covers all aspects of networks communications is the Open System Interconnection (OSI) model. An open system is a model that allows any two different systems to communicate regardless of their underlying architecture. Vendor specific protocols close off communication between different systems without requiring changes to the logic of the underlying hardware and software. An OSI model is a layered framework for the design of network systems that allows for communication across all types of computer systems. The purpose of each layer is to offer certain services to the higher layers. Layer n on one machine (source) carries on a conversation with layer n on another machine (destination).  The rules and conventions used in this conversation are collectively known as the layer n protocol. Basically, a protocol is an agreement between the two machines as how communication link should be established, maintained and released.
The users of computer network are located over a wide physical range i.e. all over the world. Therefore, to ensure that nationwide and worldwide data communication systems can be developed and are compatible to each other and international group of standards has been developed. These standards will fit into a framework which has been developed by the International Organization of Standardization (ISO). The OSI model is not a protocol rather it is a model of underlying designing a network architecture which is flexible, robust and interoperable.

ii)      The TCP/IP reference model

The TCP/IP reference model which was used earlier by ARPANET and then it is being used in the Internet. TCP/IP is a short form of transmission control protocol and interned protocol. ARPANET was a research network sponsored by the US department of Defense. It included many universities and government installations using the leased telephone lines. Later on, the satellites and radio networks were added to it. This inclusion could not be handled by the existing protocols at that time. So, new reference architecture was needed. This new architecture is known as TCP/IP reference model due to the use of the two protocols TCP and IP. While designing the new model, certain goals were to be achieved. Some of them were as follows:
i)           First design goal was to have an ability to connect multiple networks together in a seamless way.
ii)          Another goal was the network should be able to survive loss of subnet hardware with existing conversation not being broken.
iii)        Next, a flexible architecture was needed to deal successfully with the divergent requirements of various applications.

You Might also view the following Related Posts

• Networking Fundamental
• Network Topology
• Network Functions
• Network Reference Models (Network Architectures)
• Internet Security & IP Security (IPSec)
• Secure Socket Layer (SSL)

For more Posts: Click Here

Network Functions

Following are some of the important functions that a network needs to perform

1.       Switching
2.       Routing
3.       Flow control
4.       Speed
5.       Security
6.       Backup
7.       Failure monitoring
8.       Traffic monitoring
9.       Accountability
10.   Internetworking
11.   Network management

1.       Switching
Switching is defined as the ability of a network to connect different channels attached to each node to each other. This is essential for moving the traffic from incoming channel to the desired outgoing channels.

2.       Routing
Routing is defined as the ability of the network to select a path. The routing can be of different types, namely the fixed routing or alternative routing. The routing can also be classified as static routing or dynamic routing.

3.       Flow control
Flow control is the control over the rate of traffic. It is necessary in order to reduce the network congestion.

4.       Speed
The speed of different devices is different. Also the codes used by different devices are different from each other. In the digital networks, we have to allow the communication between all such devices.

5.       Security
Network security is defined as the ability of a network to disallow any unauthorized access to the network and the data travelling over it. We have to take the measures such as using passwords of use of data encryption and physical security.

6.       Backup
It is defined as the ability of a network to react to the component failures. Back up also includes sending to indicate failures or to route the traffic via some other path to avoid a failed component.

7.       Failure monitoring
It is the ability of the network to keep track of faulty and working components.

8.       Traffic monitoring
It is defined as the ability of the network to keep track of traffic levels. It is useful for the network design.

9.       Accountability
It is the ability of the network to keep a track of who is actually using the network. This is possible through the billing and charge back process. It gives us an understanding of the various users of a network. This is different from the traffic monitoring.

10.   Internetworking
When two or more networks are connected they are called internetwork of internet. Individual networks are joined into internetworks by the internetworking devices like bridges, routers and gateways.
The term internet (lower case i) is a generic term used to mean and interconnection of networks and Internet (upper case I) is the name of specific worldwide network. A common form of internet is a collection of LANs connected by a WAN. Internetworking is defined as performing the function needed for communicating with other networks in as internetwork.
The internetworking includes the following functions:
i)                    To provide routes for traffic.
ii)                   To allocate resources such as buffers and links

11.   Network management
The network management is not a one single function. It is instead a combination of many functions. It includes the following functions:
i)        To maintain the user’s list.
ii)       To maintain the addresses of the devices.
iii)     To keep an eye on changes in schedules of network.
iv)     Fault isolation.
Some of the network functions are carried out at each node and the others are needed to be carried our only by the first and the last node.

You Might also view the following Related Posts

• Networking Fundamental
• Network Topology
• Network Functions
• Network Reference Models (Network Architectures)
• Internet Security & IP Security (IPSec)
• Secure Socket Layer (SSL)

For more Posts: Click Here