Talk:Linked list/Archive 1

Archive 1

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 March 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 March 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 March 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 March 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 August 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 August 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 August 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 August 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 August 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 August 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 September 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 October 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 October 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 October 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 October 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 October 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 October 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 December 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 December 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). [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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

Building a linked list.

#include<stdio.h>
#include<conio.h>
#include<alloc.h>
struct node
{
    int val;
    struct node *ptr;
};
void main()
{
     struct node *start,*temp,*first;
     temp=0;
     clrscr();
     int data;
     char ch;
     do
     {
         start=(node*)malloc(sizeof(node));  /*creating new nodes*/
         printf("enter data:");
         scanf("%d",&data);
         start->val=data;                    /*writing data in information part of the node*/ 
         start->ptr=0;                       /*assigning null value in next pointer field of newly                    
         if(temp!=0)                           generated node*/    
         {
             temp->ptr=start;
             temp=start;
         }
         else
         {
             first=start;
             temp=start;
         }
         printf("any more (y/n):");
         scanf("\n%c",&ch);
      }
      while(ch=='y'||ch=='Y');
      printf("\nstatus of linked list after insertions is\n");
      temp=first;
      while(temp!=0)
      {
          printf("%d\n",temp->val);
          temp=temp->ptr;
      }
      getch();
}

— Preceding unsigned comment added by 122.168.205.159 (talk) 20:08, 18 July 2008 (UTC)

Inserting / Deleting in middle (with iterator)

How can this be O(1) for linked lists? What kind of preconditions are supposed here? A pointer to the middle? Matt77 (talk) 03:46, 20 July 2008 (UTC)

Implementation in JAVA

Can somebody provide a code for the implementation of linked lists (singly and doubly) in JAVA Amathew121 (talk) 14:17, 27 September 2009 (UTC)

Internal and external storage

Both linked list and reference (computer science) have a section on internal and external storage. Is it worth splitting out and merging these into a new article? Dcoetzee 11:36, 4 March 2010 (UTC)

Persistent doubly-linked lists

Doubly-linked vs. singly-linked states that doubly-linked lists can't be used as persistent data structures. Why not? 91.176.9.146 (talk) 12:26, 5 June 2010 (UTC)

Removal of table

User:Rōnin recently removed the table comparing dynamic arrays, arrays, and linked lists. It's true that we need to be clearer about separating the search time (which is linear) from the insertion time (which is constant time), but the fact that linked lists allow constant-time insertion in the middle is both obvious and widely-known; there are many sources for this e.g. [1], which I'm now citing. Constant-time insertion in the middle is actually implemented in e.g. std::list in C++, where given an iterator referring to a particular position in the list, you can insert at that position in constant time using list::insert(iterator position, const T& x). I will add back the table while clarifying the need to account for search time. (I also added a row to clarify that linked lists may only allow constant-time insertion at the beginning.) Please let me know if you have any concerns and I'll try to address them. Dcoetzee 21:41, 14 November 2010 (UTC)

Removed "complete example in C"

There was a (huge) implementation of linked lists in C in the other languages section. I have removed it, for several reasons. The first is that the article already quite adequately explains the logic behind all the common actions associated with simple linked lists in pseudo-code. The second is that more generally, WP isn't a programming implementation cookbook. I see this a lot in (simple) CS articles: people provide implementations of the discussed data structure or algorithm in language X, and then someone comes along and says (quite logically) "if we have it in programming language X, why not programming language Y?" ... this process continues and eventually the whole article is just different (often buggy) code implementations in every language under the sun -- or alternatively the talk page fills up with heated arguments about why we should have language X and not language Y.

The reality here is that reliable implementations of linked lists in C (and virtually any other combination of data structure and programming language) are widely available on-line. A compromise here would be to have, down by the External Links section, a list of links to implementations in different languages if so desired. But honestly, a second with google will lead any interested party to concrete implementations.

The article is already quite long, too. The code didn't help that at all.

Back in the day, we had this problem on the Hello world program article. It had turned into a huge mess of a gazillion examples, many of them wrong. We eventually moved almost all the examples (with the exception of the first documented one) to Wikibooks. That's a much better place to have concrete implementations.

Consider too that a wiki is a poor place to have code examples. People have varying coding abilities and understanding, but unfortunately every programmer thinks himself competent. The result has historically been that people who don't really know what they're doing edit code, and after a while there are a bunch of bugs. It's just not worth the effort.

Thanks, Eniagrom (talk) 12:11, 9 January 2011 (UTC)

Agree with this removal and all comments above, little justification is required (I was once guilty of adding this type of content myself). My Mediawiki-based LiteratePrograms wiki tried to address some of the problems with people introducing bugs into concrete code examples by test compiling it and making it available for download, but had a number of practical issues (the category tree wasn't a great way to provide different language implementations of the same algorithm - code was rarely downloaded and tested to verify it - performance was an issue). I think in the end something even more dramatic is required, a wiki that can automatically run tests and prevent changes that break them. But I digress. Dcoetzee 11:36, 15 June 2011 (UTC)

Introductory Paragraph

I reverted the intro paragraph to my previous version (with the addition of parenthesis). Below is what I reverted from and to, and my commentary on the version reverted from.

Before reverting:

"In computer science, a linked list, in its simplest form, is a data structure consisting of a group of nodes which together represent a sequence. Each node is comprised of a datum and a reference (that is, a link) to the next node in the sequence. This representation allows for efficient addition, removal, and retrieval of elements from any position in the sequence."

"Reverted" to:

In computer science, a linked list, in its simplest form, is a data structure that consists of a sequence of nodes. Operations to add nodes to the list and to remove nodes from the list are commonly implemented (usually in the form of free functions or methods). Additional operations, such as seaching the list for a node holding a specific data item, may also be implemented, either generically or, as associated specifically with the kind of list. Iterators may be implemented to facilitate operations and to traverse the list in general.

Commentary

1. Linked lists do not represent a sequence, they ARE a sequence (of nodes). 2. The focus of this article is linked lists. No need to detail 'node' here (it has its own article). 3. How fast can the last node of one million node singly-linked list be removed? It could be very inefficient unless the data structure maintains the "last link". Since the statement about efficiency is not true in general, it does not belong here. The "efficiency sentence" also downplays (by not being explicit) the relevance of list operations. 4. I added the parenthesis to convey the relevance of operations better than the original edit. 5. It's not your father's programming era anymore. A linked list can be as simple as a node or as sophisticated as an STL list, or some other implementation. Note that I specifically AVOIDED saying things like "class" or "object", but rather took the general path by just recognizing that "linked list" can be (and usually is) thought of as something structural associated with something behavioral (operations like add/remove of nodes, etc.), as is most commonly implemented as such. IOW, one is free to consider the structural part and behavioral part (e.g., a linked-list LIBRARY in C) as complementary, but separate, things, OR one can choose to view it as some kind of logical (or "physical", e.g., a class) singular thing. The goal is not to describe every element of computing as "ones and zeros", but not giving list operations some stage is doing exactly that, to some level, for the "whole picture" is not being described without recognizing list operations EXPLICITLY. (Note "list operations" as contrasted with "operations performed on a list").

TechTony (talk) 09:46, 9 August 2011 (UTC)

Re 2: Given that this is a core CS article, I think giving nodes a mere 1-sentence gloss for the introductory reader is hardly overkill. It also allows for an explanation of what the linked in linked list refers to.

Links (to other Wikipedia articles) are there for that very purpose. If you bypass that good mechanism, then you get redundancy, multiple out-of-synch definitions and a maintenance nightmare for you have to update all those "1-sentence glosses" that are all over the place, everytime the main article changes. It also clutters-up the focus of the article for those who don't need that greater level of detail. Do you want to explain what a "node" is in every linked data structure article? "nodes" are linked. If one needs more info on what a "node" is, they just click the link from any place where it says 'node' and the definition is always the latest and greatest and is not conflicting between, say, the linked list article and the red-black tree article. Note that you gave a definition of a singly-linked node and the article is about lists (though I think I remember this article being "Singly linked list", topically, perhaps because no one has organized the articles correctly: there is a "Doubly-linked list article", so it seems there is room for improvement somewhere...).

Re 3: If it's a doubly-linked list, it's quite efficient. Under singly-linked, if we're talking about any node other than the last one, removal is significantly faster than dynamic array implementations, which must shift down all intervening elements. Insertion and removal of elements are core list operations; I don't get your meaning here.

The blanket statement does not hold true though, so at the minimum, it needs to be correct before it should be on the page at all. ... Your phrasing only IMPLIES, if not downplays, the operations' significance while my phrasings bring out the operations "front and center".

Re 4: This adds nothing and isn't topical. Everything anywhere is implemented using functions/methods/subroutines.

It is not and it doesn't have to be. One can integrate the code for adding and removing nodes of a list into mainline code for a "quick and dirty" programming task without going to the level of making a reuseable data structure. The article is about linked lists in general, not just "commercial-grade, bullet-proof" linked lists. Think "theory", not one specific implementation. The article should not assume too much about the level of knowledge of the reader (Wikipedia is an encyclopedia, after all). The material is relevant to those seeking to learn about it. The complementary references "frame" the topic and add valuable information via association in addition to the bare definition. Indeed, it's that kind of thing that makes it encyclopedic rather than a terse dictionary definition. Things are related to other things. If anything, a link could maybe be used, but I think it's too general to be directed to, say, "Data structure design 101... how to make reuseable data structures, classes... etc., blah, blah".

Re 5: Generics are an implementation detail that is not essential enough to merit mention in the lede; in the article body, sure. Iterators are similarly tangential.

Those things are not tangential. They are complementary. Note that they were just referred to and not discussed in any level of detail (as, I suggest also, the way "node" should be handled within the intro). It is information within the topic area (complementary). Think "encyclopedia" rather than "dictionary". The article is not just a simple definition. Nor is the introduction. It's a lead-in and indicator of what kind of material is given in more detail in the rest of the article and "tie-ins" (when used judiciously) are one thing that makes Wikipedia a great reference tool.

--Cybercobra (talk) 11:10, 9 August 2011 (UTC)

TechTony (talk) 15:12, 9 August 2011 (UTC)

I reverted back to my edit because what you wrote was incorrect and leaving just the first sentence there leaves a stub/incomplete concept (and someone quickly noticed that). TechTony (talk) 17:04, 9 August 2011 (UTC)

What you wrote is both completely useless to the most likely readers of the article (beginning computer scientists) and omits the most important part of being a linked list: that the sequence (a mathematical abstraction) is represented in memory by nodes with next-item pointers (why its a "linked" list). I've reverted again. —David Eppstein (talk) 17:10, 9 August 2011 (UTC)

Well you reverted to something that is incorrect. (2) I disagree that the article (or any articles on Wikipedia) should be tailored immediately to an advanced audience. The "drill-down to detail" and "expansion of topic" is there on-demand: read further into the article or click on a related link within the article. Presenting information thoroughly and well so that is can be assimilated by the widest possible audience is key. (3) How you consider list operations to be "useless" to someone investigating linked lists, is baffling.(4) 'node' has a fine article of its own and doesn't need a new definition here. Wikipedia is hyperlinked so redundancy is nicely handled and articles are then maintainable. If you describe what a node is here, then you necessarily, by precedent, should describe what a node is in every linked data structure article, and it will then vary slightly in every one of them as the articles evolve. That tedium and synchronization problem is what links to other articles avoids. Length is not the only reason nor even the main reason to have separate articles. I suggest you find a way to make reference to the link work (since you are obviously averse to my attempt) instead of describing what a node is in this article.

I think this article may have evolved (is evolving) into the general article about linked lists from "singly-linked list" (note that there is a "Doubly-linked list" article) and when (if) it was that, the addition of 'singly-linked' before 'node' (in my revision) would achieve all the goals with aplomb. You also must think that the article came from the "singly-linked" article because you suggested that a 'node' is something with a 'next' link only and, of course, a doubly-linked list has also a 'previous' link. Given that, and again, I suggest you find a way to make the link to the 'node' article work, but if you are hell-bent on defining 'node' in the linked-list article, at least make correct statements and complete thoughts and synchronize with the 'node' article so that there is no conflicting information (they should be exactly the same). I'm not going to help you analyze why the statements you keep reverting to are incorrect, (but they are, think about it and you will see) because I don't think 'node' should be redundantly defined here. See my prior responses to CyberCobra for the other issues.

TechTony (talk) 18:21, 9 August 2011 (UTC)

Also re your initial premise " Linked lists do not represent a sequence, they ARE a sequence (of nodes).": this is just false. A sequence is a mathematical abstraction, a collection of items with an ordering, a function from positive integers to something else... The definition of a sequence says nothing about how it is represented in a computer. Lots of concrete data structures may be used to represent sequences: linked lists in all their different varieties, arrays, linked lists of arrays, balanced binary trees in all their varieties, etc. There may well be a place in Wikipedia for an article about sequences as abstract data types but this is not it. This article is about linked lists, a specific way of implementing that abstract data type, and taking the implementation out of the article is misguided, mistaken, wrongheaded, and just plain unhelpful. —David Eppstein (talk) 17:27, 9 August 2011 (UTC)

It is not false, even though, I changed it to "series", which also can, but doesn't have to and in this case doesn't, refer to the mathematical concept. I was probably too quick to change it. From the Free Online Dictionary, the first 3 definitions of 'sequence' given are:

1. A following of one thing after another; succession.

2. An order of succession; an arrangement.

3. A related or continuous series.

This article is not about a specific, as you say, implementation. It's a hodgepodge of an article that implies some generality and then dives into details of specific implementations even though there are fine articles (OK, the "Doubly-linked list" article) already existing. "Singly-linked list" should probably be created in the likeness of "Doubly-linked list" or maybe they should be combined (there are many possibilities). The whole set of "Linked-data structures" needs to be reworked for consistency and to minimize redundancy (a maintenance nightmare). But why stop (start) there? May as well rework the entire data structures and algorithms articles, making them consistent and non-redundant, etc. — Preceding unsigned comment added by TechTony (talk • contribs) 20:48, 9 August 2011 (UTC)

I prefer the old version of the lede, although it could use some minor adjustments. I object to to TechTony's version. Apart from being poorly phrased, it introduces too many irrelevant implementation details. In my opinion the should should focus on describing the concrete representation of a linked list, which abstract structures it can model and compare it's properties with that of other concrete structures such as arrays. —Ruud 19:21, 9 August 2011 (UTC)

Linked list operations

Contrary to what is written, there is absolutely no pseudocode for operations on doubly-linked lists. — Preceding unsigned comment added by 75.79.3.84 (talk) 02:31, 16 May 2014 (UTC)

circular list operations: " ..we use such a lastNode here"

No, "you" don't (although "L" may serve the purpose in a couple of places) and the sentence this is in is nonsensical — Preceding unsigned comment added by 75.79.3.84 (talk) 02:37, 16 May 2014 (UTC)

Random access lists

The section is useless as it does not define a key term and unhelpfully links two of them to non-existent articles. — Preceding unsigned comment added by 75.79.3.84 (talk) 03:39, 16 May 2014 (UTC)

Chart Colouring Misleading

On the chart the entry for 'Insert/delete in middle' has the linked list 'search time + Θ(1)' coloured green, supposedly indicating that this is the *best* possible approach in performance terms compared to the other algorithms. However in terms of O notation it is just as bad as a dynamic array O(n) and in practise it is far worse (reference locality). 14.202.104.48 (talk) 08:04, 3 August 2014 (UTC)

Additional lined list algorithms: Amiga hack, concurrent access, RCU

I don't have the inspiration to write some text, so dumping these here in case someone else is interested:

Exec (Amiga) made frequent use of a variant on a doubly-linked list. The list was terminated with sentinel nodes on either end which had next == NULL and prev == NULL, respectively. The list head was a three-word structure which contained the head and tail sentinels, overlapping so they shared the NULL. I.e. a node started with struct node *next, *prev;, and the head was struct node *head, *null, *tail; By ensuring that each real node had non-NULL next and previous pointers (actually called "Succ" and "Pred", for "successor" and "predecessor"), list deletion was simplified.

There could be a whole section on concurrent access to linked lists.

A simple singly-linked list can implement a lockless LIFO stack using a compare-and-swap on the head.

Read-copy-update uses linked lists extensively, inserting elements into lists to make them visible, 71.41.210.146 (talk) 15:49, 31 August 2015 (UTC)

Footnote 5 is on YouTube

This was interesting to watch, despite his missing graph.

https://www.youtube.com/watch?v=YQs6IC-vgmo#Bjarne_Stroustrup:_Why_you_should_avoid_Linked_Lists — Preceding unsigned comment added by 203.106.155.15 (talk) 09:16, 26 October 2015 (UTC)

Memory

I removed this sentence "* They have a tendency to use more memory due to [[pointer (computer science)|pointers]] requiring extra storage space" from the Disadvantages list. Since it is true of every data structure in computers (that is not an array) this is not a disadvantage, but rather a fact of nature. Nick Beeson (talk) 18:23, 28 March 2016 (UTC)

The point is, though, that they do use significantly more memory than arrays. Arrays are data structures, too. —David Eppstein (talk) 18:40, 28 March 2016 (UTC)