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
iLab 2: Office Network Expansion Connect to the iLab here. Submit your assignment to the Dropbox located on the silver tab at the top of this page. (See "Due Da

Message passing is probably the most extensively used parallel programming paradigm today. It is the mainly natural, portable and efficient approach for distributed memory systems.


QUESTION (a) Concerning agents that reduce workload, there are four agents developed using a learning approach among which is the News Filtering Agent. Name the other three age

Data Link Layer Sub layers ·  Logical Link Control (LLC) - upper layer · Handles control information, logical addressing and data · MAC (Medium Access Control) - lower layer ·

How Does Network Topology Affect The Cost And Network Performance, Computer Science.

TCP Connection Management TCP connection management encompasses the procedures for establishing and  terminating connection (FTCP is  connection oriented protocols). In TCP c

What is a protocol? The term protocol refers to a set of rules and process that govern the transmission of messages over a physical networking medium. The most common network p

Token Passing - Token Ring (IEEE 802.5) Needs that station take turns sending data Token passing coordinates process Token is a especially formatted three-byte fr

Whenever it manage a packet, IP software requires to separate the receiver address into a suffix and prefix. Classful internet addresses are self-identifying because the class of t