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
The Internet protocol mentions the rules that describe the details of how computers communicate. It exactly mentions how a packet should be formed & how a router should forward eac

In distributed data processing, explain two scenarios where vertical partitioning and horizontal partitioning are used. Distributed Data Processing The distributed data pro

Gateway A gateway  is an internetwork  device which  joins different  network  protocols  together. It woods on all  seven  layers of OSI model. Gateways are also known as  pro

Define Co-axial cable. A solid central conductor surrounded by insulating material and then by a cylindrical shield woven from fine wires is called as co-axial cable. The shie

Access Networks and Physical Media Access  networks  are the  physical  links(S) that connect  an end  systems to its edge  router. Which  is the  first router on a path  fr

What is Sonet Synchronous Optical Network is a fiber optic technology that can transmit high-speed data audio, used for text and video. Single clock handles timing of transm

Explain about star topology This topology, obviously, needs a great deal of cabling. This design gives an excellent platform for reconfiguration and trouble-shooting. Changes t

Write a report on your chosen topic that has been approved by your Lecturer. Your report should include appropriate figures, about 2000 words. Topics: 1 MAN- Metro Ethernet 2 Inte

INTRODUCTION In this part, the topic of performance evaluation shows those parameters that are devised to calculate the performances of various parallel systems. Achieving the

Concept Of Permutation Network In permutation interconnection networks the information transfer necessitates data transfer from input set of nodes to output set of nodes and po