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
Explain the meaning of Negotiation Negotiation is process of getting both sides to agree on some values or parameters to be used during communication. Maximum packet size is on

LAN HARDWARE AND PACKET FILTERING: The diagram below explain the LAN hardware LAN INTERFACE:  LAN interface operates all details of frame reception and transmis

In HTML, a tag shows the browser what to do. When you write an HTML page, you enter tags for lot of  reasons -- to change the appearance of text, to show a graphic, or to make a co

Q. What is Bipolar Encoding? - Uses three voltage levels negative, positive and zero - Zero level represents binary 0; 1s are represented with alternating positive and negat

Which form of PPP error detection on Cisco routers monitors data dropped on a link?  Ans) The Quality protocol monitors data dropped on a link. Magic Number avoids frame looping

The IP class procedure does not split the 32-bit address space into same size class and the classes do not have the same value of networks. A prefix of n bits gives 2n unique ne

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

Every input line of the combinational circuit represents an individual element of the string say xi and every output line results in the form of a sorted list. In order to attain t


Inside a device, every address mask is stored as a 32-bit number. When we submit a prefix and an address mask they use a changed form of dotted decimal addressing known CIDR addres