Talk:Linked list

From Wikipedia, the free encyclopedia

Former FA This article 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 Wikipedia:Featured article candidates/Archived nominations.
Peer review Linked list has had a peer review by Wikipedia editors which is now archived. It may contain ideas you can use to improve this article.
This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions.
B rated as B-Class on the assessment scale
Top rated as Top-importance on the assessment scale

Contents

[edit] 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. Wikipedia 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)

[edit] 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)

[edit] 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)

[edit] 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)
I just noticed this comment. Not sure what was meant by "ancient C", but it wasn't illegal in K&R C. wrp103 (Bill Pringle) 14:09, 31 October 2006 (UTC)

There is one more question regarding the program, is it possible to pass an address of a NULL pointer through a function call that you have done through your first call to add?!?

Beats me! ~: FODhruv :~ —Preceding unsigned comment added by Madireddy (talk • contribs) 05:22, 31 October 2006

Of course. A NULL pointer is a pointer whose value is zero (or whatever NULL is on the machine). You can declare a pointer and set it to NULL, then pass the address of that pointer. wrp103 (Bill Pringle) 14:09, 31 October 2006 (UTC)

[edit] 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)

[edit] 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). [Your typing speed is too fast......][Are you really a programmer??? ]

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)

[edit] 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)

[edit] 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)

I've added an SVG diagram of a circularly linked list. I think I might also redo the rest of the diagrams in SVG, if that's alright with everyone. Also, I favor merging the Circular list article with this one (is there still an effort to do that?). Finally, I have never heard of the term "end pointer" used with circularly linked lists, and using Google I cannot find any websites that use the term. Does anyone have a reference for this term? If not, I'll delete that sentence. Lasindi 10:38, 3 June 2007 (UTC)

I would call it the access pointer. Managing the circular linked list is all about the access pointer, since the access pointer can establish the pointed node as the head node, or the tail node. This is my Eureka moment after leaving college for 15 years. MegaHasher 08:41, 21 July 2007 (UTC)

[edit] 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 ((q) && (p->data==key)) {
            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)

[edit] Pointer to visualizations classified "link spam"

In the "External Links" section, I added a link to an academic repository of linked list visualizations that was removed 3 hours later as "link spam". Understanding that my intentions may have been misinterpreted, I reverted the edit and put a note of explanation in the history. Once again, the link has been removed, so I feel it's time to move this to Talk.

From Reverting: Reverting should be used primarily for fighting vandalism. From Vandalism: Vandalism is any addition, deletion, or change to content made in a deliberate attempt to reduce the quality of the encyclopedia. I think it's clear that the link is not vandalism, so this should not be the reason for the revert.

So let's talk: Why do you believe the link is spam? I added to the bottom of the list, my entry was in line with the phrasing and format of the other links in the list, and I don't understand why the link is any worse than, for example, the next lowest link on the list: Linked Lists Tutorial with diagrams and Java code example. I think we all care about the quality of the encyclopedia here, so I'd rather see some consensus than start a revert war. Thank. --VTBassMatt 13:26, 18 July 2006 (UTC)

I think there is a big difference between the mycsresource link and the Algoviz page. The first tells the reader what a linked list is, has some nice pictures to help visualize different types of lists, etc. The one that was deleted is a tabular list of entries, many of which apparently have little merit, from reading the table. The others are supposed to be good for teaching the concept. If a reader wants to learn more about the subject, I would rather take them to a page where they can learn, rather than having to search through a table looking for something useful. The table itself doesn't seem to be well constructed (IMHO): the text is rambling at places, contains speculations, and gives no clear indication of the quality of the packages. Were these the only examples they could find? Are the entries in some kind of order?
Frankly, there are several entries still in the External links section that I don't think should be there, but I guess I missed them when they were added. Shortly after I started working on Wikipedia, I added a reference to a generic Linked List package in C that I make available for my students (and others) that I've used in a number of fairly complex packages. It was removed as link spam, partly because I was the author, but at that time the preference was for institutional resources rather than personal ones. A couple of the entries that are there look like something somebody threw together and maybe it will work, but maybe it won't.
BTW - As I responded to you on my talk page, you should not revert something and mark it as a minor edit. That might have raised a red flag for some people. wrp103 (Bill Pringle) 14:37, 18 July 2006 (UTC)
I have to agree with Bill here. The Algoviz page appears to be off-topic as it concentrates on visualization techniques rather than linked lists. I think the ten minutes of attributing relationships show that the topic is visualization rather than any particular sub-topic. Those additions might be better placed in an article on visualization techniques and internally linked to the various treatise on the individual topics themselves. Cleaning up those external links would be a good idea on your part to keep a topic page on visualization technique from being regarded as a walled garden in the future. Ste4k 19:07, 18 July 2006 (UTC)
Had I linked to the algoviz page, I would agree that it's off-topic, and in fact one of the future plans is to write up a good Wikipedia entry on algoviz (if one doesn't already exist--I haven't looked), where I'd certainly link to our group's front page. However, our work isn't about visualization techniques. It's a catalog of available visualizations broken down by topic, and the link posted was directly to the linked lists category. Bill's argument that the linked lists page isn't nearly presentable is a valid criticism, but I think you must have followed some of the links on the page I referenced to make the argument that it was about visualization and not linked lists. What gave you the idea our work is about techniques? Someday it may be, but for now it's just a catalog.
And yes, obviously MY topic is visualization, but each of the links points at the relevant collection of visualizations for that algorithm/data structure, and the whole point of the AlgoViz group is to connect visualizations with people trying to understand data structures. When I'm exposed to a new data structure, the first thing I do is hit the Wikipedia page to get an idea of how it works--presumably others do as well.
Sorry this is straying off-topic--your arguments just hit a little too close to personal attacks for me not to respond. HAND. --VTBassMatt 21:35, 18 July 2006 (UTC)

[edit] small issue with deleting a node

The article states that deleting a node in a singly linked list with only the reference to the node you want to delete isn't possible... if the target is not the tail, then won't this work?

public boolean deleteThis(){

if(next = null);

//fail because "this = null" doesn't work

return false;

this.data = next.data;

this.link = next.link;

return true;

} —Preceding unsigned comment added by 137.112.141.152 (talk) 04:49, 19 October 2006

That approach would create a memory leak. wrp103 (Bill Pringle) 13:03, 19 October 2006 (UTC)
This approach has some validity. In a garbage-collected language (the code looks like Java), this would not create a memory link. Otherwise, you could very easily assign the "next" reference to a temporary reference variable, and then de-allocate it. Something like this in C++:
bool node::deleteThis() {
  if (next == NULL)
    //fail because "this == null" doesn't work
    return false;
  node *temp = next;
  data = next->data;
  next = next->next;
  delete temp;
  return true;
}
However, it still has several drawbacks. It requires copying of the "data" value, which for some datatypes in some languages is expensive or problematic. Also, more importantly, it would invalidate any iterators that point to the next node. --Spoon! (talk) 10:16, 5 December 2007 (UTC)

[edit] VBSCRIPT

The examples should be given in Vbscript. C++ and C are too difficult to grasp! Remember that Wikipedia is read by a number of people with very different backgrounds, not only geeks, programmers and the like.

Thank you. 201.19.142.218 18:20, 31 October 2006 (UTC)

I disagree. C is the closest thign to a lingua franca programmers have. As long as we keep it simple and straightforward anyone who can figure out the vbscript should be able to figure out the C. (We could obfuscate the C but we could also obfuscate the vbscript if we wanted to. I've known programmers who did it withOUT wanting to!) RJFJR 21:01, 31 October 2006 (UTC)

[edit] Patent

U.S. Patent #7028023 now identifies a Linked list as a legitimate invention. Any addition into this article about this? Patent 7028023 Meternx01 18:05, 30 November 2006 (UTC)

Actually if you read into the patent information more, you will find that the patent was probably incorrectly labeled as a 'linked list', but in fact it is a new adaptation of it. The concept behind the patented version seems to be a linked list that can be traversed in multiple orders, depending on how many "auxiliary" pointers are added to each node in the list. Thus, if you follow the primary pointers, you traverse the list in one order; if you follow the first auxiliary pointer, you traverse in another order; if there is a second auxiliary pointer and you follow it, you traverse the list in a third order; and so on and so forth. —The preceding unsigned comment was added by 129.116.46.59 (talk) 04:05, 20 March 2007 (UTC).
But surely being able to traverse the list in any order is the whole point of a linked list -- that's what makes a linked list different from a list (see e.g. The C Programming Language, Second Edition. by Brian W. Kernighan and Dennis M. Ritchie. Prentice Hall, Inc., 1988.). All the patent appears to describe is a doubly-linked list (it also implies that triply-linked or further linked lists are a possibility).Rnt20 12:20, 20 March 2007 (UTC)

[edit] Inserition into array O(N)

I'm unsure if that's correct. You can add an element in the linked list in O(1) if you keep a pointer to the proper element.. Same way, keeping an index of the last set value in an array, you can add elements in O(1) as well. —The preceding unsigned comment was added by Stdazi (talk • contribs) 20:39, 11 January 2007.

)

While that's technically possible, all textbooks (including the one I'm using: Data Structures, Algorithms, and Applications in Java by Sartaj Sahni) tell you that linked list operations are constant time. -- Sprocter

I think there might be some confusion over terms here. All linked list operations can be done in constant time, but presumably that does not include searching for a given node. The functions "add_node" and "delete_node", for example, will take a fixed amount of time (except for very minor differences if it is the head or tail node). However, a function "insert_sorted" that finds the appropriate insertion point and then does the insert will take linear time. -- wrp103 (Bill Pringle) (Talk) 20:13, 2 July 2007 (UTC)
I do not understand the OP's comment. You can insert an element anywhere in a linked list in O(1) if you have a pointer to the proper location. You cannot do that with an array; maybe only at the end. Because to insert an element, you need to shift all subsequent elements to the right. --Spoon! (talk) 10:20, 5 December 2007 (UTC)

[edit] Just unclear

In this section I found a sample code, written in programming language C, that explained linked list. I found that funtion list_add() should not return a pointer to the data structure (not by funtion name anyhow).

I don't understand why it has to return that either. Could somebody explain that to me? Thanks, Lysergsaure 18:57, 20 November 2007 (UTC). —Preceding unsigned comment added by Lysergsaure (talk • contribs)
The function in the sample code returns a pointer to the new node that was created and added to the list. The function is passed a pointer to the head of the list, and the data elements needed for the new node. It needs to be passed a pointer to the head in the event that the new node is placed at the head of the list. One reason that the newly created node might be returned is so that the caller can add a node and then update the fields.
There are lots of ways to implement a linked list. I personally don't care for the method in that example, so if some other way makes more sense to you, then use that method. -- wrp103 (Bill Pringle) (Talk) 23:35, 20 November 2007 (UTC)

[edit] Add references

Please add Glist from GObject as a doubly-list API in C. —Preceding unsigned comment added by 124.104.3.74 (talk) 02:45, 8 January 2008 (UTC)

[edit] double circular linked list is wrong/confusing

In the double circular linked list section the article states:

To insert at the beginning we simply "insertAfter(list.lastNode, node)"

but the list can initially be empty and a test is necessary much like the code for insertEnd() immediatly above it.

Maybe a better way would be to implement insertBeginning almost like the existing code for insertEnd (without the last line advancing the lastNode, and stating that "insertEnd is insertBeginning with a lastNode shift (list.lastNode:=list.lastNode.next)"

Rjds.ferreira (talk) 12:10, 7 April 2008 (UTC)