[RESOLVED] DATA STRUCTURE (Help with assignment)

[freeze_sr]

I have this assignment for the subject of Data Structures. I just don't know what the question is about, and frankly i don't understand the subject at all. If anybody can help me out, guide me, please do. I give my utmost respect to those who do.

-----------------------------------------------------------------------
Question:

Discuss the advantages, if any, of a two-way list over a one-way list for each of the following operations.

1. Traversing the list to process each node
2. Deleting a node whose location LOC is given
3. Searching an unsorted list for a given element ITEM
4. Inserting a node before the node with a given LOC
5. Inserting a node after the node with a given location LOC

In your opinion which way is more useful?

-----------------------------------------------------------------------

[si_the_geek]

It seems to be referring to a "list" as a group of items which not only contain a value, but also a pointer to the next item (for one-way) or next and previous (for two-way).

If so, that would make the methods for some of the operations noticeably different.

[Shaggy Hiker]

Doubly linked list vs singly linked list.

1) As long as you are traversing front to back only, there is no advantage of double over single. However, if you want to go backwards in a singly linked list, even for a single step, you no longer know where you came from, because the current node contains no information as to how you got there. A doubly linked list lets you know which item to transition to next, regardless of which way you are going.

2) When you delete a node, you need to update the node that was pointing to the node you are deleting. In a singly linked list, you don't know which node you need to update, because by having one node, you don't know which other node, if any, points to it.

3) No clue. If you were to search by simply starting at the beginning and going to the end, then a singly linked list would be the same as a doubly linked list. If you have some other kind of search algorithm, then it might make a difference.

4) Roughly the same issue as 2. In a doubly linked list, you would go to node LOC, and the LastItem for the new node would be the LastItem of LOC, while the NewItem for the new node would be LOC. The LastItem of LOC would change to the new node. If you were doing the same thing for a singly linked list, you could do about the same steps, or even less, but you would have to work with node LOC-1.

5) Same as 4, but the task would actually be easier for a singly linked list, as the NextItem for the new node would become whatever was in LOC.NextItem, while LOC.NextItem would change to the new node.

[freeze_sr]

Thanks guys.

Shaggy Hiker, if I use your post as the answer to my assignment, will it be what they want? (word for word).

(this is only 1 out of 3 questions and i have completed the rest)

Also, which way is more useful?

[Shaggy Hiker]

I can't possibly answer either question. The first one requires understanding the desires of people I have never met, while the second is just a bit bizarre. I think that doubly linked lists seem somewhat more useful, yet in all the years I have programmed, I have never actually needed either one. I do remember reading some comparison of linked lists vs. arrays, and the like, but I don't remember the arguments. Best answer: Ignore the whole thing and use List (of Type) in any .NET language.

However, if you google on doubly linked lists, you should get about a billion hits, some of which are probably valuable.