answersLogoWhite

0

As compared with doubly-linked lists, one disadvantage is that singly-linked lists can only be efficiently traversed in one direction. Finding the (n - 1)th element, given only a pointer to the nth, requires scanning the list from the first element up to the (n - 1)th. Thus (if memory is too limited to permit tricks such as creating a reversed list) to iterate over the entire list in reverse order would require n + (n - 1) + ... + 1 = n(n + 1)/2 link traversals, which grows quadratically with n. Obviously for a doubly-linked list the time merely grows linearly with n.

A down-side of all linked lists versus arrays is that random access can be inefficient; the time taken to find an element with a randomly chosen index grows in direct proportion to the list's length (since we must scan from one of the ends). In contrast, an array allows us to index directly to the elements with simple pointer arithmetic, in a time independent of the array's size - at least in an idealised environment.

User Avatar

Wiki User

12y ago

What else can I help you with?

Continue Learning about Engineering

Explain Pseudo code for circular linked list?

write pseudocode for link list


What is the advantage of doubly linked list over Doubly linked list?

A doubly linked list can be traversed in both directions (forward and backward). A singly linked list can only be traversed in one direction. A node on a doubly linked list may be deleted with little trouble, since we have pointers to the previous and next nodes. A node on a singly linked list cannot be removed unless we have the pointer to its predecessor. On the flip side however, a doubly linked list needs more operations while inserting or deleting and it needs more space (to store the extra pointer).


What are the basic types of link list in java?

linear circular double linked linear double linked circular Knowing the names does not help much when your teacher will require you to actually know what the names mean. Start reading. Programming requires lots of reading.


What is the advantage of circular queue over simple queue?

Circular queue have less memory consuption as compared to linear queue because while doing insertion after deletion operation it allocate an extra space the first remaining vacant but in circular queue the first is used as it comes immediate after the last.


What are the Circular singly linked list applications in real life?

best example is trains...where each coach is connected to next coach except the engine and the last coach..when we need to add a coach we need to move to the right position and adjust the connecting point suitably!!

Related Questions

what are the differences between singly link list and doubly link list?

singly linked list stores only the address of next node while doubly linked list stores the address of previous node and next node and hence it is called doubly linked list. In singly linked list only forward traversing is possible while in doubly linked list forward and backward traversal is possible.


How do you write a program to add node at specific position in singly link list?

new->next = current; current->next = new;


Programfor addition of two polynomial using circular link list?

dsd


What is a singly linked linear list?

A singly linked list is a linked list which only provides links in "one direction". Using a metaphor, a singly linked list is a one way street, while a doubly linked list is a two way street. Once you move forward in a singly linked list, there is no way to go backwards unless you kept your reference/pointer from before. A singly linked list would look like this: start ----> node1---->node2---->node3 ----> NULL You will see that node2 only has a link forward to node3 - it does not have a link backwards to node1, even though node1 has a link forwards to node2. To prevent us from permanently losing access to portions of the linked list, we generally keep a reference/pointer to "start". A doubly linked list would have twice the number of pointers/references as a singly linked list - making it very inefficient to store small datatypes. On the other hand, it would be possible to move both forwards and backwards with a doubly linked list because you have links pointing both forwards and backwards.


Explain Pseudo code for circular linked list?

write pseudocode for link list


Why the drop of water is always circular in shape?

Surface tension ; see relevant link .


How do you plot a circular curve around a point?

The link does not work so it is not possible to answer the question.


What is the difference between circular linklist and linklist?

In a circular linked list every node is connected to another node. In a non-circular linked list. There are definitely starting and ending nodes are lacking an incoming and outgoing link, respectively.


What is current legislation?

In the US, current copyright legislation is found in Circular 92 (link below).


What are the disadvantages of gmaw?

GMAW is an arc welding process. See related link.


What are the types of link list you have?

Single, double, circular, circular double. Each of these can also be threaded, making it easier to traverse the list in order, but a tree is more appropriate for that type of structure.


What is the advantage of doubly linked list over Doubly linked list?

A doubly linked list can be traversed in both directions (forward and backward). A singly linked list can only be traversed in one direction. A node on a doubly linked list may be deleted with little trouble, since we have pointers to the previous and next nodes. A node on a singly linked list cannot be removed unless we have the pointer to its predecessor. On the flip side however, a doubly linked list needs more operations while inserting or deleting and it needs more space (to store the extra pointer).