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
Switched Ethernet In switched networks a switch device identifies the destination address and routes the frame to the specific port to which the destination station is conn

Q. Explain Full Duplex data transmission? - Have two separate Communication channels as well as use each one for simplex Data traffic (in different directions). - If this is

FDDI Media Access Control Unlike CSMA/CD networks such like Ethernet token-passing networks are deterministic--you are able to calculate the maximum time that will pass before

Discuss the interdependence of networking hardware and software. Is it possible to have one without the other?

Question 1 Explain FDM and TDM with example Question 2 Define B-ISDN and explain its services Question 3 What is symmetric key cryptography? Describe one symmetric

IPv6 packet Format The format  of an IPv6 header is shown  in figure. Although IPv6 addresses are four  times  the size  of IPv4 address  the basic  IPv6 header is only twice

To relieve some programming burden, project 5 is a group project that two students can form a group to do and submit one report. In your submitted report, please specify who is you

What is the difference between trigger and rule? Ans) The triggers are known as implicitly by database generated events, whereas stored procedures are known as explicitly by cli

Categorization according to pipeline configuration According to the configuration of a pipeline, the below categories are recognized under this classification: Unifunct

Unused Reserved This  is a 6 bite field  reserved for future use.