Misplaced Pages

Revision as of 17:13, 4 July 2006

Template:FACfailed is deprecated, and is preserved only for historical reasons. Please see Template:Article history instead.

This article (or a previous version) is a former featured article candidate. Please view its sub-page to see why the nomination did not succeed. For older candidates, please check the Misplaced Pages:Featured article candidates/Archived nominations.

Linked list received a peer review by Misplaced Pages editors, which is now archived. It may contain ideas you can use to improve this article.

Older discussions

how can you distinguish the pointer "next" and "prev" ?

Good job, Deco! Making trashy looking pics always make people do nice ones. :) You might also wanna check In-order traversal if you have time. BL 06:52, Jan 23, 2004 (UTC)

Hmmm, the last code example is much too obscure, and also uses a singly-linked list, as opposed to what is shown. I'll fix this eventually if no one else gets to it first.

Deco 00:57, 8 Mar 2004 (UTC)

I should say that causes potential problem, especially when visiting the previous node. i will try to fix it. --Yacht 01:31, Mar 8, 2004 (UTC)

This is good, although in my opinion the code could be made simpler, eliminating some of the system calls that might appear strange to a C programmer. The pointer manipulations also appear to come out of nowhere for someone inexperienced with linked lists. I think I'll insert pseudocode for basic manipulations of a few types of linked lists.

Deco 01:31, 11 Mar 2004 (UTC)

"The pointer manipulations also appear to come out of nowhere for someone inexperienced with linked lists", i don't know. but i think it would be better to initialize a pointer to NULL. security reason... pseudocode is good, but need to make note that it's unexecutable. --Yacht 04:24, Mar 11, 2004 (UTC)

this operation ":=" looks like that in Pascal. :O --Yacht 07:56, Mar 11, 2004 (UTC)

I think it's good to be unambiguous in pseudocode; I've seen several use the := notation. An alternative is <-, but that's less familiar.

Deco 20:41, 11 Mar 2004 (UTC)

The singly-linked list figure is somewhat misleading, since it suggests that the last element contains the address of a special node (rather than containing a special address that points to no node).Jorge Stolfi 20:08, 23 Mar 2004 (UTC)

The difference is really an implementation detail; it could be implemented using a sentinel node, instead. I chose this notation because I've seen it in books, and it makes it clear that the field still is a pointer, it just doesn't point anywhere interesting.

I would like to modify the doubly-linked list diagram, though, so that the pointers don't appear to be pointing to cells inside the nodes, but to the nodes as a whole, as far as this is possible. If you imagine the next and prev pointers are literally pointing to each other, you can imagine the confusion.

Deco 13:58, 24 Mar 2004 (UTC)

I think there's nothing about the main algorithms description that prevents it from being generic, since the data can in fact be a pointer or, as pointed out, be determined by template parameters or parametric polymorphism. The code in this part is also entirely in C, which is inconsistent. I'm going to erase most of it, since it's mostly redundant - I hope there are no objections. Deco 13:34, 27 Aug 2004 (UTC)

The explanations here are also extremely C-specific ("a car is a void pointer"), and in many cases explains how to do things that are a bad idea, such as indexes by the first letter. If you start doing this sort of thing you might as well use a trie. Also, even in C, it's possible to use macros to allow a generic linked list data structure with internal storage; I know, I've done it. The advertising links to one particular author's linked list implementation are also offensive to me.

I will incorporate a discussion of internal versus external storage, even if I'm repeating content from reference, and I'll talk about putting single data items in multiple lists, but these are the only things I'll be taking away from this added content.

On another note, I think the new C linked list example may be longer than necessary, but it isn't bad or out of context, so I'm leaving it alone. Deco 13:54, 27 Aug 2004 (UTC)

I don't want to sound defensive, but the reason I added the generic linked list is that I've seen tons of examples of the first kind of linked list, but seldom have seen of the kind I added. Most of thI don't recall any of the text books on data structures that I've seen that method. (If you know of one, let me know ... I would consider it for my course.) I would really like to see the alternative method available someplace. Comments?

I didn't think a link to my generic linked list package would be offensive, nor did I think of it as an "ad". I don't make any money from it, and the package is under a creative commons license, and I encourage my students to use it rather than write their own. I thought that if somebody wanted a ready-made package, I would point them to it. It's not that I think it is a great package, but it works, so I keep using it. If I had to do it again I would do it differently (but that's almost always true ;^)

I'm new to wiki ... what are the guidelines to referencing external sites that contain more info?

Building an index based on the first letter is a good (IMHO) way to partition a linked list so that you can start your search closer to your target. Depending on the size of the list, the index might be for the first few letters. Partial indecies are used lots of places if the entries are in a sorted order, even in non-linked list applications. I recall a program I worked with that used partial indecies to access offset information on waypoints and airways that were stored in various files.

BTW - a skip list originally is built by linking every "n" nodes together, but as soon as the actual list is modified, that relationship is broken. Finding the 'nth' node in a linked list probably shouldn't be done with a skip list. Even if the list is static, you have to watch out for the end of the list, unless the spacing of each skip level is a modulo of the list size.

If I need direct access to a linked list, what I have done sometimes is to ingest information and insert it into a linked list. I then allocate a dynamic array of pointers, and then loop through the list setting the address in the array. I can then use the array to access the 'nth' node. From then. on, the list must be stable (or at least you have to handle any insertions/deletions) If the list is especially large, I will use an array of linked list (nodes) based on a partial index (first 'n' letters), maintain the size of each list, and then sequentially search the list that contains the element (by adding up the sizes of the sublists until I exceed 'n').

wrp103 (Bill Pringle) | Talk]]

I'm sorry if my changes seemed rude, and your efforst are appreciated, but really, I found your content primarily redundant and extremely specific to the C language. In many languages, such as C++ and ML, a generic linked list data structure can be written in precisely the way the existing description explains. Even in C, it's possible to write a generic linked list data structure in this way, either using internal storage together with macros, or using external storage - the original description did not exclude the data begin a generic reference to data, and so includes your description, although not written in C - unless there's some other difference I hadn't noted. Also, as I pointed out in the new sections, internal storage is not incompatible with placing objects in multiple linked lists either.

As for your points about indices, they are certainly useful in a variety of contexts, and I my above points about them may have been in error, but they're not intrinsically related to linked lists, and so probably belong in some article about indexes. All data structures can have indexes constructed on them. A link somewhere may be appropriate.

Your points about skip lists are accurate and appreciated; please edit, but keep it terse, as the main article is skip list.

As for the link, this is a contentious point. I follow a policy of including only highly authoritative or popular external links, or article references (in their own section). Some are more flexible, but in this case I assure you that many, many people have written packages identical to yours - I have one on my own website under a less restrictive license. Many of them are used a lot more widely. Misplaced Pages used to contain links to a site called GreatSnakes containing algorithm descriptions and code samples, which I erased also, because it was a brand new site. I think we should, like an algorithms book, provide the simplest possible description, and leave raw implementations to Google and repositories like SourceForge.

This is just my own view though, and there has been no consensus on this matter. I imagine others might see it as personal advertising for exposure though. Deco 02:13, 28 Aug 2004 (UTC)

Don't worry, you have to try a lot harder to offend me. ;^)

I see (and agree with) most of your points. I'm used to doing examples in C because (a) I like C, and (b) where I teach, the assumption is that all the students know C (which is taught in the "intro" course for those without programming backgrounds) and anyone with programming experience has most likely run across something like C, C++, Java, etc.

I teach a course on data structures and algorithms, and have been very frustrated with what text books are available, that have poor examples and/or even worse code samples. This has been especially true for sections on linked lists, which always use examples of internal storage, and never even mention how to use external storage. If anyone has suggestions, please let me know.

As for personal promotion, I would like to think that wasn't a motive. (but I would be the last to know! ;^)

wrp103 (Bill Pringle) | Talk]] 12:53, 28 Aug 2004 (UTC)

Linked list using an array

I am thinking of adding a linked list varaint that uses an array instead of next and prev pointers. It has some minor advantages but is probably not used widely. Since the article is long and is in good shape, I want to know what you think first. (I am suspecting there might be someone who would say such implementation is unpopular thus somehow irrelevant.) -- Taku 13:54, Aug 28, 2004 (UTC)

Can you describe the variant here first? I'm not familiar with it. Deco 17:37, 28 Aug 2004 (UTC)

If you are talking about using array indecies instead of pointers, that is the only way to build a linked list when working with a language that doesn't support pointers. The very first linked list I ever wrote was back in the '60s using FORTRAN!

wrp103 (Bill Pringle) | Talk]] 19:00, 28 Aug 2004 (UTC)

Linked list record

While having a record that contains the head and tail pointers for a linked list is useful, I would claim that this is obvious, and that its discussion is too C-centric and in the wrong section. Also, using a current pointer inside such a record is a poor design, because it makes it dangerous to iterate through the list twice at one time, which can occur even in two seemingly unrelated pieces of code operating on the same list. For now I cut all this. Deco 18:21, 23 Sep 2004 (UTC)

I didn't notice this when you did it. I don't agree that it is obvious, especially to a beginner. I am not aware of any text books that mention a linked list data structure. Most of the texts that I have used don't even mention external linked lists, but rather include links within some existing data structure.

Maybe you're right, but if we're going to mention the idea of encapsulating the abstract data structure in this way it should be done higher up where the representations of various types of linked lists and their operations are first introduced.

About external linked lists: linked lists with external storage are a special case of internal linked list, in that their data is a reference. The only other change this involves is deallocating data when nodes are destroyed in languages without garbage collection. Therefore this material is in a very formal sense redundant. It's useful to mention the tradeoffs, but they're not specific to linked lists (they were already discussed in reference). The widely-held belief that linked lists with internal storage cannot be made generic is a fallacy, even in C, as I explain in the article. I also think the code examples are probably a bit too long and have too many comments (textbooks never comment every single line; comments should serve to summarize and explain at a high level, but this is a matter of opinion.) I leave the section in as a simple example of the general tradeoffs between internal and external storage. Deco 19:16, 6 Oct 2004 (UTC)

As for the current link, that is the only way I can think of to implement a generic iterator, which I mentioned in the text. (Yes, the client program can store the current link in local memory, but I'm not talking about that.) It also allows you to create the concept of a recordset cursor. If you have two tasks accessing the list, then they could each have their own LinkList data structure, since it simply contains links to the head and tail nodes (in addition to current). This could cause problems if new head or tail items are inserted, but using dummy/sentinel head & tail elements should help that.

An iterator for an ordinary linked list need only store a reference to the current node. The record describing the linked list itself should contain a head and tail pointer, but not a current pointer, as this implies there is a single current node for the list at any one time. I think somewhere higher up something should be added like this:

I don't agree, but that is why there are more than two flavors of ice cream. ;^) Consider implementing an iterator for a circular linked list. When to you know you are done? When the current node is the tail node. Multiple tasks modifying the same linked list raises all kinds of concurrency problems, especially if it is a double linked list. With a single linked list, you just change the next pointer of the previous cell after you have set up the new node, and there shouldn't be a problem, assuming the assignment is an atomic operation. However, with a double linked list, you better have some sort of locking mechanism in place. Because of that, I assumed in my LinkList package that if somebody was iterating through the list, it was a single task, so the only thing that changed was the current pointer. Using that approach, the client program only has one thing to keep track of ... the LinkList pointer, which contains head, tail, and current. Again, it is a matter of preference, and hopefully each person implements whatever they are comfortable with. I think my approach is easier for a beginner to use, which is what most of my students are. wrp103 (Bill Pringle) - Talk 20:49, 6 Oct 2004 (UTC)

Part of the point a circular linked list is that you can start iterating around the complete list from any point — you just need two iterators and the ability to compare them for equality. They have no head or tail. In applications with additional constraints like concurrency you just add information to the iterator, such as a reference to the list's lock. Even in single-threaded applications, iterators are important for reentrancy; the simplest example is building a loop over all pairs of elements from the list. A more subtle and error-prone example is passing a list to a function which iterates over it while iterating over it. Separating the list and its iterators isn't difficult, even for beginners; I'd argue it also helps better understand and isolate the concepts behind an abstract list. Deco 21:05, 6 Oct 2004 (UTC)

Er, that said, if you want to insert or delete nodes passing just the iterator, then it does require a reference to the list itself. Note that it does not suffice to add head and tail to the iterator's record, because then updates to head and tail through one iterator aren't reflected in other active iterators. Deco 21:08, 6 Oct 2004 (UTC)

Linked lists implement the abstract data stucture of a list with sequential access. It's useful to hide the implementation details of the linked list behind two records that represent abstract concepts applying to all data structures implementing a sequential access list, namely the list itself, and an iterator, which indicates a position in the list. These are particularly simple for linked lists:

            record list {
                node head      // Reference to first node in list
                node tail      // For doubly-linked lists, last node in list
            }
            record iterator {
                node current   // Reference to node at current position
            }

For other sequential list data structures, these records might contain different data.

If you know of any texts that do mention linked list structures (and/or discuss internal/external design) I would like to know about them. While I'm at it, can you recommend any text books for Programming Languages Concepts? I'm not happy with my current one, and wouldn't mind finding a better text. wrp103 (Bill Pringle) - Talk 18:44, 6 Oct 2004 (UTC)

A pretty thorough discussion of linked lists is given in CLRS (Introduction to Algorithms, ISBN 0070131511), pages 204-208, which is a very good and very popular textbook in general. As for programming language concepts, in my opinion there's no substitute for actually using languages in several paradigms to accomplish nontrivial tasks — but the web page for a course at my university offers a number of good references. Deco 19:16, 6 Oct 2004 (UTC)

main function in C

There is no problem with declaring main to take no arguments: it is legal according to both C89 and C99, and is also the usage in the C article itself. The argv and argc arguments would be unused in the function if they were added, so I think that keeping them in the example doesn't add anything. Since it's not illegal to declare main as taking no arguments, I don't see any reason why we shouldn't do it. Neilc 01:17, 29 Nov 2004 (UTC)

I guess then it's ok. Either way, main (void) or main (int argc, char *argv), it's illegal in ancient C anyhow. -- Taku 04:48, Nov 30, 2004 (UTC)

Referencing linked lists

I don't think the problem of how to pass a linked list to a procedure is limited to C (though I could be wrong) -- it seems to me that any language which does not treat the list as a built-in datatype is going to have lists referenced by their head and/or tail elements, and will sometimes run into the tricky problem of having to double-dereference those elements if the operation could change the identity of the head/tail elements. Since this is a problem common to more node-based data structures than just the linked list, however, perhaps it would be best to address it in data structure and mention it briefly here? -- Antaeus Feldspar 16:59, 26 Dec 2004 (UTC)

Well, the issue is not limited to C, per se, but only in C does it seem that programmers are constantly reinventing the wheel when it comes to datatypes instead of creating abstractions (this issue would never arise in a C++ program using the STL, for example). A better way to do it is to embed the head and/or tail into an opaque data structure representing the list itself and pass a reference to this around. If it must go somewhere though, I would choose reference (computer science); data structure is far too general. Deco 09:41, 28 Dec 2004 (UTC)

Why I correct the pseudocodes

The main reason is I want to make the pseudocode more clear.

Some function are doing repeating things, for example, in insertBeginning of "Doubly linked list", the head assignment is repeated because the function insertBefore have done the checking.

Some parameter are missing, for example, how do the program know the head and end without the transmission of parameters???

Moreover, removing an element which is after/before a node is more practical than removing an element at current node. - (anonymous user)

Hi there, I apologize if I offended you. I reverted your changes because they were almost all incorrect or redundant/unnecessary. Here's some explanations.

• There is no need for a "removeAfter" or "removeBefore" function in a doubly-linked list; one can simply invoke "remove" on node.next or node.prev. They also don't make sense for the head/tail node, introducing annoying special cases.
• The original remove function handled one-element lists perfectly fine, as the trailing comment of that section explicitly points out. We do not need "removeone".
• The original circular list iteration code was correct, simpler, and more general - I don't see why you'd want to specify the ending node rather than the starting node. This might deserve explaining.
• There's no need for an "insertBefore" method in a circular linked list - just do an insertAfter node.prev. There's no need for "insertone" either - the insertAfter method already contains code to deal with that. (This code could be removed, but one or the other, not both.) This might also deserve explaining.
• Similarly, there is no need for two remove functions, or for a one-element list. The one "remove" method deals with all this in a much simpler way.
• I think "last node" is clearer than "final node", and that "insertBeginning" or "insertFront" is clearer than "insertHeading" (the word "heading" means like an article header, nothing to do with this.)
• I think "nodeBeingRemoved" is clearer than "oldNode", as "oldNode", although commonly used in programs, suggests the existence of two different nodes, an "old" node and a "new" node, which is not the case.
• In "We also need a function to insert a node at the beginning of a possibly-empty list", the removal of "at the beginning of" makes the purpose of the function less clear.

If there's anything I would keep it would be perhaps the renaming of "head" and "tail", but I would name them "firstNode" and "lastNode". I'll go ahead and make this change.

To answer your specific complaints:

• The null check in insertBeginning is necessary; otherwise it would not know to update "head" and "tail" correctly. Similarly for the other "redundant" null checks. An alternative approach is to pass them in to the insert method by reference, but this complicates other calls.
• I was thinking of head and tail as either global or instance variables, or as variables of some linked list data structure. I admit, this is unclear and I can definitely do something about it.

I apologize again if I offended you, and I'll try to incorporate at least some of your comments to help clarify the code. Thanks for your contributions. Deco 07:32, 5 December 2005 (UTC)

Ok, but you should correct the pseudocodes, instead of reverting all the changes......

I could reply some part of your comment.

"The original circular list iteration code was correct, simpler, and more general - I don't see why you'd want to specify the ending node rather than the starting node. This might deserve explaining."

This is because the start pointer can be found by endNode.next , and the insertion before the endNode.next is difficult than the insertion after the endNode.next, especially in singly-circular-linked list. This specification enables this conclusion "insertion before the START of the list is easier than before the END of the list".

"There is no need for a "removeAfter" or "removeBefore" function in a doubly-linked list; one can simply invoke "remove" on node.next or node.prev. They also don't make sense for the head/tail node, introducing annoying special cases."

I think you could correct this part, but you should know my pseudocodes of "removeAfter" or "removeBefore" do not use both node.prev and node.next, i.e. in "removeAfter", there is no node.prev at the right hand side of ":=", and in "removeBefore", there is no node.next at the right hand side of ":=". This coding is convenient for converting the linked type of the list, and sometimes when the program iterates through that list forwardly, the deletion of the next element may be useful; and when the program iterates through that list backwardly, the deletion of the previous element may be useful.

"* I think "nodeBeingRemoved" is clearer than "oldNode", as "oldNode", although commonly used in programs, suggests the existence of two different nodes, an "old" node and a "new" node, which is not the case."

You are right, but i suggest "obsoleteNode" is "stronger".

Okay, I'm sorry - I think everything is fixed now. I took the previous version and made the following changes:

• I replaced "head" and "tail" with firstNode and lastNode throughout.
• I put "head" and "tail" into a "List" structure which is passed into the functions. This should make it clear where they're coming from and that they're being modified permanently.
• I added some text explaining why the methods you added aren't needed, since this isn't obvious.
• I used lastNode instead of firstNode in the circularly-linked list. I didn't consider how this could simplify things for singly-linked circularly-linked lists, this is a good point.
• Changed "nodeBeingRemoved" to "obsoleteNode", I like that name.

I understand the advantage of your approach of having both a removeAfter and a removeBefore, since it somewhat simplifies deleting nodes in a list as you iterate over it, but most mainstream libraries offer just a "remove" method and either make it return the next node or make the caller save the next node in the iteration. I also think "remove" is a great demonstration of the power of doubly-linked lists to simplify operations, even if you're only iterating in one direction.

I hope this satisfies both of us, and I do appreciate your feedback. Sorry for acting so drastically before. Saved these changes and now will reincorporate some of your textual changes, which were also good. Deco 08:06, 5 December 2005 (UTC)

Fixed some other random stuff - please tell me if you have any other suggestions, or just go ahead and change stuff. I apologize again for being so aggressive. Deco 08:39, 5 December 2005 (UTC)

I am sorry to "correct" the pseudocodes too much, and I am satisfied with the current version that edited by you (not me). I believe that pseudocodes should be easy to read, especially for the novice user (may be I).

Don't feel bad, I overreacted. Even if you are a novice, you are among the intended audience for the article, so it's very important that it's clear to you. I think your feedback has definitely had a positive effect. (And yes, I'm really a programmer, I really have no idea why I type so fast. :-) Deco 19:15, 5 December 2005 (UTC)

Very Helpful

Thanks. Although some information on how it is used for different programming languages would be nice (I just used this article for Computer Science homework, had trouble with the insert after, I was close and probably could have figured it out after another 10 minutes or so, but I have a crapload of homework) JONJONAUG 00:56, 17 February 2006 (UTC)

Hi JONJONAUG. We appreciate your positive feedback, but I'm afraid I'm unclear on what your suggestion is. Could you rephrase? Are you asking for more sample implementations or what? Deco 05:44, 17 February 2006 (UTC)

Yeah. JONJONAUG 00:00, 18 February 2006 (UTC)

Circularly-linked list

The two sub-sections of this section do not seem to provide any non-obvious information that is not already mentioned in either the main circularly-link list section, or the single/doubly linked list section above.

I suggest just removing the two sub sections in order to make the article more concise. What do other people think? Should anything be added to the main circularly-linked list section if the subsections are removed? Thelem 18:31, 6 April 2006 (UTC)

That sounds like a good idea. You might consider moving a summary of the content from the subsections up, although I'm not sure I agree with what they claim are "usual". wrp103 (Bill Pringle) 19:23, 6 April 2006 (UTC)

not possible is incorrect.

In the discussion of single link lists, the article is stating incorrectly that various operations cannot be performed. Ste4k 18:17, 2 July 2006 (UTC)

I suppose it's more correct to say that they can't be performed in constant time, or that they require linear time. Deco 11:07, 4 July 2006 (UTC)

The article is making assumptions about the application as well as the number of variables one might use. Consider the following:

#include <stdlib.h>
struct some_rec {
    int data;
    struct some_rec *next;
};
struct some_rec *head=NULL;
/*-----------------------*/
int del_prev(int key) {
struct some_rec *p,*q,*r;
int deleted=0;
    p=head;
    q=r=NULL;
    while (p) {
        if (p->data==key) {
            if (q) {
                if (r) r->next=p;
                    else head=p;
                (void)free(q);
                deleted=1;
                p=NULL;
            } 
        } else {
            r=q;
            q=p;
            p=p->next;
        }
    }
    return deleted;
}

There are some other assumptions made in the article as well. Ste4k 17:13, 4 July 2006 (UTC)

• Misplaced Pages featured article candidates (contested)
• Old requests for peer review