Linked list for parallel algorithms, Computer Networking

Linked List

A linked list is a data structure composed of zero or extra nodes linked by pointers. Each node consists of two parts, as shown in Figure: info field having specific information and next field having address of next node. First node is pointed by an external pointer called head. Last node called tail node does not have address of any node. Therefore, its next field points to null. Linked list with zero nodes is known as null linked list.

1692_linked list.png

                                                                                               Linked List

A large number of operations can be presented using the linked list. For some of the operations like insertion or deletion of the latest data, linked list takes constant time, but it is time consuming for a few other operations like searching a data. We are giving here an instance where linked list is used:

Example 3:

Given a linear linked list, rank the list elements in terms of the distance from each to the last element.

A parallel algorithm for this query is given here. The algorithm assumes there is p number of processors.

Algorithm:

Processor j, 0≤ j

else rank[j] =1 endif

while rank[next[first]]≠0 Processor j, 0≤ j

rank[j]=rank[j]+rank[next[j]]

next[j]=next[next[j]]

endwhile

The working of this algorithm is showing by the following diagram:

1344_Finding rank of elements.png

                                                                    Finding rank of elements

Posted Date: 3/2/2013 7:35:55 AM | Location : United States







Related Discussions:- Linked list for parallel algorithms, Assignment Help, Ask Question on Linked list for parallel algorithms, Get Answer, Expert's Help, Linked list for parallel algorithms Discussions

Write discussion on Linked list for parallel algorithms
Your posts are moderated
Related Questions
ARP - Address Resolution Protocol It is the protocol that traces IP addresses to MAC addresses. RARP - Reverse Address Resolution Protocol It is the protocol within the TC

Question: (a) What do you meant by the term ‘LAN'? How is a LAN different from a WAN? (b) Explain three types of cables which are commonly used with LANs. (c) Three com

UNIX For Multiprocessor System:- The UNIX operating system for a multiprocessor system has a number of additional features as compared to the normal UNIX operating system.  Let

To use a subnet or classless address, table under routers and hosts that have address must keep two pieces of information with every address: the 32-bit address itself and another

Hardware Cost It indicates to the cost concerned in the functioning of an interconnection network. It comprises the cost of arbiter unit, connectors, switches, interface logic

Token Ring Implementation Sequence of 150-ohm shielded twisted-pairs sections Output port on every station connected to input port on the next Frame is passed to


Q. Illustrate Data-Link Layer in osi layers model? Data-Link Layer: This layer takes the data messages or frames from the Network Layer and gives for their actual transmissio

Parallel Balance Point In order to implement a parallel algorithm on a parallel computer, K number of processors is needed. It may be noted that the given input is assigned to