CODEWITHSUNDEEP
data-structureslinked-list
user3205479
user3205479

Reputation: 1523

What is the need for asymmetric linked list

I am studying data structures. I have come across Asymmetric linked list which states that it is a special type of double linked list in which 

1. next link points to next node address 
2. prev link points to current node address itself

But I wonder, 

1. what are the advantages we get by designing such linked list? 
2. what kind of applications this would be suitable for?

Could anyone kindly explain more on Asymmetric linked list. I googled but I could not find relevent answers. Thank you.

Source :http://en.wikipedia.org/wiki/Doubly_linked_list#Asymmetric_doubly-linked_list

Upvotes: 3

Views: 604

Answers (3)

tigrou
tigrou

Reputation: 4516

Because a picture worth thousands words :

enter image description here

As you can see, "previous" field is referencing "next", rather than previous element itself. This make little difference between nodes, except for first element : the previous field can point to the head rather than pointing to the last element (circular list) or be null.

The main advantage is for insertion and deletion : you don't need to take care of head and check if element is first one. Just having a single pointer to an element is enough to perform an insert or a delete to the list.

One disadvantage vs circular list : the only way to get last element (eg: to implement some "add last" operation) is to loop through the whole list.

You also lose the ability to loop through the list in reverse way (because no previous pointer), except if all elements have same size and you are allowed to do pointer arithmetic (as it is in C/C++).

Upvotes: 0

Sergey Sokolov
Sergey Sokolov

Reputation: 76

I agree the Wiki page is misleading. Here is the difference between LL and ALL:

Open Linked List:

node.next = nextNode
node.prev = prevNode

Asymmetric Linked List:

node.next = nextNode
node.prev = prevNode.next

Note the difference prevNode vs prevNode.next.

While pointing to a pointer within node still preserves the ability to traverse list backwards (you can get prevNode address by subtracting from prevNode.next) it may simplify insertion and deletion operations on the list, especially on the start element.

Upvotes: 1

Bruce
Bruce

Reputation: 11

Given a node pointer from a double linked list, we can traverse all the nodes by the 'prev' and 'next', while a single linked list cannot do that if the pointer provided didn;t point to the first node.

E.g, delete a node from linked list. With single linked list, you have to traverse the list from head to find the specific node, and also need to record the prev node against the specific node, which causes the time complexity O(n). However, with double linked list, you can perform the delete with the specific node with the constant time.

In short, given a specific node, for single linked list, if we need to use its prev node information, the traverse wiht O(n) from the head is inevitable, while double lined list doesn't.

By the way, list in STL and LinkedList in Java are implemented with double linked list.

Upvotes: 0

Related Questions