Linked Lists

[I_Love_My_Vans]

Hi there faithful servants.

I am doing an assignment for college and a question was asked to "give examples of where linked lists would be employed"

Now I am struggling with this one, I have a few examples found via Google however I wish to know what you guys think, where would a linked list be used?


Thanks People

[I_Love_My_Vans]

Thanks for moving

ILMV

[Shaggy Hiker]

Linked lists are faster than arrays for inserting and deleting objects from the middle. Arrays are faster for inserting or deleting at the ends. Linked lists can be re-ordered without a great deal of effort, while sorting of arrays can take a fair amount of memory swappage. I guess I don't have any specific example, but I have always thought linked lists were mostly used where insertions and deletions were likely to occur in the middle rather than the end.

[FunkyDexter]

To add to that, resizing is far less intensive with a linked list (it's implicit in the insertion or removal with no extra action required).

[I_Love_My_Vans]

What examples though, for example i know Microsoft Access (relational databses) uses linked lists.

[Shaggy Hiker]

The original question is phrased in such a way that specific apps are not necessarily the right answer. To the question "give examples of where linked lists would be employed", a reasonable answer would be: They would be used in places where there will be a large number of insertions and deletions from within the middle of a collection that also needs to be traversed at good speeds.

Better might be to say "frequent" rather than "large number", since a large number of items inserted all at once would not necessarily give any advantage to a linked list.

The part about traversing quickly is just there because the whole purpose of "linking" is that one item directs you to the next, so that the chain can be traversed. If there is no particular order to the items, then you can always stick stuff onto the end of an array, but that just goes back to insertions and deletions happening in the middle. Such a situation would only arise when the order of the items in the collection is important.

[Al42]

A telephone/address list would be one example. A zipcode list would be an example where you wouldn't usually use a linked list (too much overhead for the occasional insertion).

[Ellis Dee]

The problem with linked lists is that you can't search them efficiently. The only way to search for an item is to compare your search term against every single element in the list.

Effectively, a linked list is an ordered array that allows cheap additions and deletions at the cost of extremely expensive searches. They are basically useless if you can't add an item until you first verify it doesn't already exist, so you wouldn't want to implement a linked list of unique items.

I'm trying to think of a real-world application for a linked list, but having never seen one used in 20 years of programming, I'm coming up blank.

[tr333]

I'm trying to think of a real-world application for a linked list, but having never seen one used in 20 years of programming, I'm coming up blank.

Obviously someone has thought of a use for a linked list... they took out a patent on it

[Shaggy Hiker]

I've never used one, either, but a small sorted list would be efficient as a linked list. How tough would it be to search a sorted linked list? You go to the middle, choose up or down, and repeat. You should zero in on the right place in only a few steps for most lists. You then are inserting into the middle of a sorted list. Alternatively, you could have a sorted array, add an item to the end, and re-sort, but that seems like it would be wild overkill. Never have used one, though, so that's sheer speculation.

[Ellis Dee]

Obviously someone has thought of a use for a linked list... they took out a patent on it

Heh, nobody ever said usefulness was a requirement for obtaining a patent. Someone filed a patent for a combination cheese grater / rat trap, fer cryin' out loud.

I've never used one, either, but a small sorted list would be efficient as a linked list. How tough would it be to search a sorted linked list? You go to the middle, choose up or down, and repeat. You should zero in on the right place in only a few steps for most lists. You then are inserting into the middle of a sorted list. Alternatively, you could have a sorted array, add an item to the end, and re-sort, but that seems like it would be wild overkill. Never have used one, though, so that's sheer speculation.

The operation you're describing sounds like a binary search, which you can't do on a linked list because linked lists can only be accessed sequentially. Binary searches require random access. (eg: "Go to the middle.")

[superbovine]

Something like a printer queue can be implemented as a link-list. For that matter any queue, i.e. circular queue or pirority can be some variation of a link-list.

Also a binary tree can be implemented using a linked-list or something very similar to it.

[Shaggy Hiker]

The operation you're describing sounds like a binary search, which you can't do on a linked list because linked lists can only be accessed sequentially. Binary searches require random access. (eg: "Go to the middle.")

That's right, I was thinking about a form of goofy cheating type of linked list, not a real one.

[Ellis Dee]

Hey, I just thought of an example of when I personally implemented a linked list structure in an application. I never associated it with linked lists because the "pointers" go in reverse, but hey, that's close enough.

The idea is for when you have a dynamic user-defined data hierarchy. The treeview control is particularly well-suited for the user interface of such a scheme.

Consider an audio file library, as an (imperfect) example. You have thousands of songs, but as a programmer how do you want to organize them? You don't; you want to let the user define his music "folders", and let him move his songs around however he likes. Sample configurations:

Genre
--Song

Album
--Song

Genre
--Band
----Album
------Song

You get the idea. This is an imperfect example because you'd probably want the ability to flip between those groupings, but imagine a dataset where flipping around the structures wouldn't be a desired feature; only the ability for the user to dynamically create an ideal structure is required.

You could set up you "folders" (let's call them "groups") in a single table like this:

tblGroup
GroupID
ParentID
GroupName

It's not relational, but it's very flexible. Each group points to a different group (in the same table) as its parent, except for root groups which store either 0 or Null in the ParentID field.

Displaying this to the user is a trivial matter using a treeview control. Iterate through a recordset of the groups where ParentID=0, adding each group one a time. When adding each group, first recursively call the function for each child group you find, then add all the actual data. Pseudocode:

Sub PopulateTreeview()
    TreeView.Clear
    PopulateTreeviewRecurse 0
End Sub

Sub PopulateTreeviewRecurse(Parent As Long)
    For Each Group Where Group.ParentID = Parent
        PopulateTreeviewRecurse Group.GroupID
        For Each Item Where Item.GroupID = Group.GroupID
            Treeview.Add Item
        Next
    Next
End Sub

This counts as a linked list, right?

[SeanK]

What is the definition of a "Linked List"?

[CVMichael]

I used a Linked List when I made my web spider.

I insert in the link list 1 link, then the web spider would go to that link, and get all the links within that link and append to link list. When done, go to next item, and get the links, then append, and so on...

I a few minutes the link list will have thousands of items, in a few hours, undrets of thousands, and even up to a million links (depending on your internet connection).

When you have THAT many items, and you would have to resize an array every time you insert an item, it would take a few seconds just to resize the array.... but with a Link List, there is no time delay when the items increase in number.

So... I think this is a very good example.

[Ellis Dee]

On further reflection, strictly speaking none of these examples are true linked lists; they are trees. (No doubt there is an official name, but it ain't a linked list.)

The web spider, the song database, the phone tree; all of these include one-to-many relationships, where any given node can be pointed to by more than one child nodes.

In a true linked list, there is a one-to-one relationship between the nodes. (Going both ways if it's a double linked list.) In a nutshell, you start at the beginning and iterate through each node. When you get to the last node, you've touched every single node exactly once without ever backtracking.

This is very different from the tree structures given as examples so far. I have to revert back to my original stance, where I can't think of a single practical use for a linked list. That's not to say there isn't one; I just don't know of any.

[penagate]

A hook chain.
http://blogs.msdn.com/oldnewthing/ar...09/693280.aspx

[CVMichael]

On further reflection, strictly speaking none of these examples are true linked lists; they are trees. (No doubt there is an official name, but it ain't a linked list.)

The web spider...

I think you missunderstood how the web spider works.... Wehn it gets the links it appends to the SAME linked list, and it's gonna add to the key also. This is to prevent having duplicate links, so it never visits the same link twice.
If I was to add to a tree, I would never have that information (knowing it is a duplicate)

[Ellis Dee]

I sure did misunderstand. But after a more careful reading, it sounds like you're just using a collection. (Or are you using a database?)

Regardless of whether you're using an array, collection, or database to store the internet links, I don't see why you would need to link them together at all. Do you actually link them in a chain? And if so, do you ever bother to iterate that chain?

You mention that it would take too long to redimension an array. That's probably true, but you also mention that you verify each new link to be added is unique. That is a very expensive task for a linked list; it might be more efficient to keep the internet links in a sorted database and then seek each new link to verify it's unique.

[CVMichael]

I sure did misunderstand. But after a more careful reading, it sounds like you're just using a collection. (Or are you using a database?)

At first, I used the VB collection wich is basically like a linked list, but performance was really reduced when it got to ~ 50,000 items. Then I made my own linked list in C++ and I designed it in such a way so performance does not get reduced as more items are added, but I never tested it with more than ~ 200,000 items (I did not need to, at the time). Also, I was not good with databases back then when I did this.

But next time I will do this, I will definitelly use a database (and not Access that's for sure..., probably I will use SQL Server)

Regardless.... the question in the first thread was when to use a linked list... and i'm just saying that a linked list can be used in a situation like this... (for web spider)