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
Connectionless Multiplexing  and De multiplexing Java program running in a host can create a UDP socket  with the  line Datagram's socket my socket =  new datagram's socket

Connecting Devices of bridges - Five kinds: - Repeaters - Hubs - Bridges - Two- and three-layer switches - Repeaters and hubs - layer one of Internet model -

CAUSES OF FAILURES Every failure has a well-defined cause.  Any system or device has an inherent strength or capacity to resist failures. This depends on design, material, man

What are the working of software team The software team has to learn every bit of things related to computers. Since different users work on different platforms and application

MULTICASTING : The answer to above problem is multicasting. It is the normal form of broadcasting. It acts like broadcasting however it does not broadcast frames automatically

What is Microwave? Microwaves have been used in data communications. Microwave has a higher frequency than radio waves and thus can handle larger amounts of data.

SONET SDH To satisfy the  requirements  of ever increasing data rate  for diverse applications, ANS developed  a standard known as synchronous optical  network by utili

An Internet address (IP address) is a unique 32-bit binary number given to a host and used for all interaction with the host. Each packet transmit across an Internet contains the 3

Q. Show the Security Policy as well Integrated Security ? Security policy is on paper statement describing what assets are to be protected and why who is responsible and which

1.  A virtual memory system has a virtual address space of 4 Gigabytes and a page size of 8 Kilobytes.  Each page table entry occupies 4 bytes.   a)  How many bits remain unchanged