Linked list for parallel algorithms, Computer Networking

Assignment Help:

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


Related Discussions:- Linked list for parallel algorithms

Differentiate between rarp and arp, TCP/IP Protocol Suite 1. What is th...

TCP/IP Protocol Suite 1. What is the concept of Multi-protocol encapsulation in ATM networks? 2. Differentiate between RARP and ARP. 3. Differentiate TDP and UDP. 4. D

The internet layer - fundamentals of networks, The Internet Layer The ...

The Internet Layer The  internet  layer is  responsible  for routing the data  packets  to the appropriate  destination. Internet protocol (IP) is responsible for ensuring dat

State token ring implementation, Token Ring Implementation Sequence...

Token Ring Implementation Sequence of 150-ohm shielded twisted-pairs sections Output port on every station connected to input port on the next Frame is passed to

What is the effect on the security of the password, Question: (a) What...

Question: (a) What is a script kiddie? Is it a significant security threat, and why? (b) Assume that UNIX uses the user login name in lieu of the traditional salt, what is

Network comp. architecture, Write discussion on Associative mapping - compu...

Write discussion on Associative mapping - computer architecture

Compare delays in packet switching and circuit switching, In this question,...

In this question, you will compare delays in packet switching (i.e. in IP networks), in circuit switching (i.e. in PSTN telephony) and in virtual circuit packet switching (i.e. in

Error detecting code - parity bit, Error Detecting Code - Parity bit: ...

Error Detecting Code - Parity bit: The general idea for achieving error detection and correction is to add some redundancy (i.e., some extra data) to a message, which receiver

Importance of reliability engineering, The progress of any industry and ind...

The progress of any industry and indeed countries as well, today is linked to the effective performance of its equipments, processes and systems. Reliability engineering, not only

Quantity of numbers that a system administrator has to enter, In order to l...

In order to limit the quantity of numbers that a system administrator has to enter, Cisco can use which abbreviation to show 0.0.0.0?  Ans) Cisco uses host to state 0.0.0.0. Thi

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd