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
Microcells As cells become smaller, antennas move from the tops of tall buildings or hills, to the tops of small buildings or the sides of large buildings, and finally to lamp

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

- The project should include a web server, and an example webpage - Webserver should continue to accept multiple requests from client browser - Webserver should print out logs: how

What is a binary semaphore? What is its use? A binary semaphore is takes only 0 and 1 as values. They are used to execute mutual exclusion and synchronize concurrent p

What are the concerns of the Physical Layer? Physical layer coordinates the functions needed to transmit a bit stream over a physical medium. a. Physical characteristics of in

Q. Show Ethernet Media standard? - The cables and connector specifications utilized to support Ethernet implementations are derived from the EIA/TIA (Electronic Industries Asso

802.11 FHSS Frequency-hopping spread spectrum in a 2.4 GHz band Carrier sends on one frequency for short duration then hops to another frequency for same duration, hops agai


FDDI Media FDDI signifies a 100 Mbps token-passing dual-ring LAN that uses a fiber-optic transmission medium. Even though it operates at faster speeds FDDI is similar to Tok

Q. What is Aspects of Security? - Security Attack: Any action whichcompromises the security of information owned by an organization. - Security Mechanism: A mechanism th