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
Q. Show the Model for Network Access Security? Model for Network Access Security (1) Gatekeeper functions comprise Password-based login authentications. (2)

Which layer is responsible for coordinating communication between systems Ans) The Session layer performs the following: Responsible for establishing and maintaining connections

Advantages of LS over DV algorithm There  are a number of advantages to link  state  protocols  especially when  compared to  the distance vector based  routing  protocols. The

Can I get help for traffic congestion anlysis using GIS

What is difference between Baseband and Broadband Transmission in ccna? Ans) In a baseband transmission, the entire bandwidth of the cable is consumed by a one signal. In bro

What is Kerberos in Networking? It is an authentication service developed at the Massachusetts Institute of Technology. Kerberos uses encryption to stop intruders from discover

SWITCHING: A switched LAN has a single electronic device that sends frames among the connected devices. A hub with several ports simulates a single shared phase. However a swi

What is the benefit of using classless addressing over classfull addressing scheme?

What is the main purpose of OSPF? OSPF, or Open Shortest Path First, is a link-state routing protocol that uses routing tables to verify the best possible path for data exchang