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
As there will be more devices there will be more traffic of information. We can include capacity to WAN by adding more links and packet switches. Packet switches use not have compu

Describe the concept of intradomain and interdomain routing protocols?



Explain the working of ISDN Stands for Integrated Services Digital Network. It is a way to move more data over existing regular phone lines. ISDN is rapidly becoming availab

Issues with Bridges Connecting Different LANs - Frame format - differences in frame structure, fields used (example Ethernet to Token Ring) - Payload size - size of data en

Hubs/Repeaters Hubs/Repeaters are used to connect together two or more network segments of any media type. In larger design, signal quality starts to deteriorate as segment exc

IPv6 The  internet  engineering task force begin  the effort to develop a successor  protocols  to IPv4 in the early  1990 is an internet  layer protocols  for packet  switched


You must write the 6 programs described below. All of these are command-line tools that follow the Unix style of passing switches and arguments on the command line. As such, your p