Misplaced Pages

Talk:Linked list: Difference between revisions

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Browse history interactively← Previous editContent deleted Content addedVisualWikitext
Revision as of 19:23, 6 April 2006 editWrp103 (talk | contribs)7,574 edits →Circularly-linked list: agree← Previous edit Latest revision as of 19:27, 15 July 2024 edit undoQwerfjkl (bot) (talk | contribs)Bots, Mass message senders4,012,747 editsm Removed deprecated parameters in {{Talk header}} that are now handled automatically (Task 30)Tag: paws [2.2] 
(135 intermediate revisions by 68 users not shown)
Line 1: Line 1:
{{FACfailed}} {{Talk header}}
{{User:MiszaBot/config
{{oldpeerreview}}
| archiveheader = {{tan}}
| counter = 1
| algo = old(730d)
| maxarchivesize = 75k
| archive = Talk:Linked list/Archive %(counter)d
| minthreadsleft = 5
| minthreadstoarchive = 2
}}
{{ArticleHistory
|action1=PR
|action1date=10 December 2004
|action1result=reviewed
|action1link=Misplaced Pages:Peer review/Linked list/archive1
|action1oldid=
|action2=FAC
|action2date=2005-01-29, 18:18:11
|action2result=not promoted
|action2link=Misplaced Pages:Featured article candidates/Linked list/archive1
|action2oldid=9779829
|currentstatus=FFAC}}
{{WikiProject banner shell|class=C|vital=yes|1=
{{WikiProject Computing|importance=High}}
{{WikiProject Computer science|importance=Top}}
}}
{{Broken anchors|links=
* <nowiki>]</nowiki>
}}


== Older discussions == == Patent ==


U.S. Patent #7028023 now identifies a Linked list as a legitimate invention. Any addition into this article about this?
how can you distinguish the pointer "next" and "prev" ?
] 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. <small>—The preceding ] comment was added by ] (]) 04:05, 20 March 2007 (UTC).</small><!-- HagermanBot Auto-Unsigned -->
Good job, Deco! Making trashy looking pics always make people do nice ones. :) You might also wanna check ] if you have time. ] 06:52, Jan 23, 2004 (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).] 12:20, 20 March 2007 (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.


Some other references in order to landing Triply Linked List concept
] 00:57, 8 Mar 2004 (UTC)


https://math.stackexchange.com/questions/512581/what-is-a-cycle-hypergraph
:I should say that causes potential problem, especially when visiting the previous node. i will try to fix it. --] 01:31, Mar 8, 2004 (UTC)
https://steemitimages.com/DQmXBnRMWd6k4GSfD4F9Q1TAM42nXheiJTLcPLWMJZttp5g/C2RD3ASWEAUZObM.jpg


"Directed hypergraphs and applications"
:: 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.
Giorgio Gallo, Giustino Longo and Stefano Pallottino,Sang Nguyen
https://core.ac.uk/download/pdf/81159246.pdf


"Cycles in Hypergraphs"
::] 01:31, 11 Mar 2004 (UTC)
Gabor N. Sarkozy, page 12 "Tight cycles"
https://web.cs.wpi.edu/~gsarkozy/Cikkek/Rio08.pdf <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding ] comment added by ] (]) 06:17, 15 June 2019 (UTC)</small> <!--Autosigned by SineBot-->


== External links modified ==
:"''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. --] 04:24, Mar 11, 2004 (UTC)


Hello fellow Wikipedians,
::this operation ":=" looks like that in ]. :O --] 07:56, Mar 11, 2004 (UTC)


I have just modified one external link on ]. Please take a moment to review . If you have any questions, or need the bot to ignore the links, or the page altogether, please visit ] for additional information. I made the following changes:
::: 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.
*Added archive https://web.archive.org/web/20150923015150/http://www.osronline.com/article.cfm?article=499 to http://www.osronline.com/article.cfm?article=499
::: ] 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).] 20:08, 23 Mar 2004 (UTC)


When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.
: 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.


{{sourcecheck|checked=false|needhelp=}}
: 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.


Cheers.—] <span style="color:green;font-family:Rockwell">(])</span> 11:55, 16 May 2017 (UTC)
: ] 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. ] 13:34, 27 Aug 2004 (UTC)


== missed the style Linux uses in the kernel ==
: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 ]. 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 ], 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. ] 13:54, 27 Aug 2004 (UTC)


Objects can be on multiple lists, using generic list code, while still keeping the list data within the objects.
----
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?


This is done via the container_of macro. It takes a pointer to a list_head, the struct type that the list_head is embedded in, and the name of the list_head within that struct. It gives back a pointer to the containing struct. Generic list handling code doesn't need to care that the list_head could be just one of many in the middle of a struct.
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 ;^)


] (]) 09:14, 5 July 2020 (UTC)
I'm new to wiki ... what are the guidelines to referencing external sites that contain more info?


== Reversal ==
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.


] recently removed a badly-sourced and badly-described section on (destructively) reversing singly-linked lists, but with an incorrect edit summary saying that this is impossible. It is actually a standard problem, going back at least to 1973; see Appendix A of http://i.stanford.edu/pub/cstr/reports/cs/tr/76/544/CS-TR-76-544.pdf, where an algorithm for this problem is credited to Ed McCreight. We should probably describe it. But I agree that there was nothing worth saving in the removed content. —] (]) 00:27, 23 October 2021 (UTC)
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.
:I didn't say it was impossible. It's not a normal function associated with a singly linked list. And if you have the need to reverse the order then it's probably the wrong data structure to be using. ] (]) 00:53, 23 October 2021 (UTC)
::Probably true, although if you want a method where you can move around within the list, insert and delete elements at the (single) moving point, and not have too much overhead from changing all the pointers around, a singly-linked ] (pointing outwards in both directions from the finger) might be a reasonable way to go, and the list reversal algorithm more or less comes for free with that. In any case, that's all beside the main point, which is that this is still standard material on this data structure that might sometimes be useful for job applicants in particular to have seen. —] (]) 06:48, 23 October 2021 (UTC)


== Data Type ==
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').
Do linked lists definitionally only store ints? Like any ADT, you should be able to create an implementation for any data type, but the article explicitly states they are for integers. Is this just about original design, simplification, or is the article saying non-int uses are against the purpose of the structure? ] (]) 17:16, 30 March 2023 (UTC)

] | ]]]

: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 ].
:As for the link, this is a contentious point. I follow a policy of including only highly authoritative or popular external links, or article references (in their own section). Some are more flexible, but in this case I assure you that many, many people have written packages identical to yours - I have one on my own website under a less restrictive license. Many of them are used a lot more widely. Misplaced Pages used to contain links to a site called GreatSnakes containing algorithm descriptions and code samples, which I erased also, because it was a brand new site. I think we should, like an algorithms book, provide the simplest possible description, and leave raw implementations to Google and repositories like SourceForge.
:This is just my own view though, and there has been no consensus on this matter. I imagine others might see it as personal advertising for exposure though. ] 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! ;^)
::] | ]]] 12:53, 28 Aug 2004 (UTC)

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

:Can you describe the variant here first? I'm not familiar with it. ] 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!
:] | ]]] 19:00, 28 Aug 2004 (UTC)

==Linked list record==

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

::::Linked lists implement the ] 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 ? I'm not happy with my current one, and wouldn't mind finding a better text. ] - ] 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 &mdash; but offers a number of good references. ] 19:16, 6 Oct 2004 (UTC)

== main function in C ==

There is no problem with declaring <code>main</code> to take no arguments: it is legal according to both C89 and C99, and is also the usage in the ] article itself. The <code>argv</code> and <code>argc</code> 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 <code>main</code> as taking no arguments, I don't see any reason why we shouldn't do it. ] 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. -- ] 04:48, Nov 30, 2004 (UTC)

== Referencing linked lists ==

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

== Why I correct the pseudocodes ==

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

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

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

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

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

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

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

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

I apologize again if I offended you, and I'll try to incorporate at least some of your comments to help clarify the code. Thanks for your contributions. ] 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. ] 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. ] 08:39, 5 December 2005 (UTC)

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

:Don't feel bad, I overreacted. Even if you are a novice, you are among the intended audience for the article, so it's very important that it's clear to you. I think your feedback has definitely had a positive effect. (And yes, I'm really a programmer, I really have no idea why I type so fast. :-) ] 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) ] 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? ] 05:44, 17 February 2006 (UTC)
:Yeah. ] 00:00, 18 February 2006 (UTC)

== Circularly-linked list ==

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

I suggest just removing the two sub sections in order to make the article more concise. What do other people think? Should anything be added to the main circularly-linked list section if the subsections are removed?
] 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". ] 19:23, 6 April 2006 (UTC)

Latest revision as of 19:27, 15 July 2024

This is the talk page for discussing improvements to the Linked list article.
This is not a forum for general discussion of the article's subject.
Article policies
Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL
Archives: 1Auto-archiving period: 2 years 

Former featured article candidateLinked list is a former featured article candidate. Please view the links under Article milestones below to see why the nomination was archived. For older candidates, please check the archive.
Article milestones
DateProcessResult
December 10, 2004Peer reviewReviewed
January 29, 2005Featured article candidateNot promoted
Current status: Former featured article candidate
This  level-5 vital article is rated C-class on Misplaced Pages's content assessment scale.
It is of interest to the following WikiProjects:
WikiProject iconComputing High‑importance
WikiProject iconThis article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Misplaced Pages. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing
HighThis article has been rated as High-importance on the project's importance scale.
WikiProject iconComputer science Top‑importance
WikiProject iconThis article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Misplaced Pages. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science
TopThis article has been rated as Top-importance on the project's importance scale.
Things you can help WikiProject Computer science with:

 Here are some tasks awaiting attention:
Tip: Anchors are case-sensitive in most browsers.

This article links to one or more target anchors that no longer exist.

  • ]
Please help fix the broken anchors. You can remove this template after fixing the problems. | Reporting errors

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)

Some other references in order to landing Triply Linked List concept

https://math.stackexchange.com/questions/512581/what-is-a-cycle-hypergraph https://steemitimages.com/DQmXBnRMWd6k4GSfD4F9Q1TAM42nXheiJTLcPLWMJZttp5g/C2RD3ASWEAUZObM.jpg

"Directed hypergraphs and applications" Giorgio Gallo, Giustino Longo and Stefano Pallottino,Sang Nguyen https://core.ac.uk/download/pdf/81159246.pdf

"Cycles in Hypergraphs" Gabor N. Sarkozy, page 12 "Tight cycles" https://web.cs.wpi.edu/~gsarkozy/Cikkek/Rio08.pdf — Preceding unsigned comment added by 181.203.58.210 (talk) 06:17, 15 June 2019 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Linked list. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

  • If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
  • If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 11:55, 16 May 2017 (UTC)

missed the style Linux uses in the kernel

Objects can be on multiple lists, using generic list code, while still keeping the list data within the objects.

This is done via the container_of macro. It takes a pointer to a list_head, the struct type that the list_head is embedded in, and the name of the list_head within that struct. It gives back a pointer to the containing struct. Generic list handling code doesn't need to care that the list_head could be just one of many in the middle of a struct.

97.104.89.121 (talk) 09:14, 5 July 2020 (UTC)

Reversal

User:Meters recently removed a badly-sourced and badly-described section on (destructively) reversing singly-linked lists, but with an incorrect edit summary saying that this is impossible. It is actually a standard problem, going back at least to 1973; see Appendix A of http://i.stanford.edu/pub/cstr/reports/cs/tr/76/544/CS-TR-76-544.pdf, where an algorithm for this problem is credited to Ed McCreight. We should probably describe it. But I agree that there was nothing worth saving in the removed content. —David Eppstein (talk) 00:27, 23 October 2021 (UTC)

I didn't say it was impossible. It's not a normal function associated with a singly linked list. And if you have the need to reverse the order then it's probably the wrong data structure to be using. Meters (talk) 00:53, 23 October 2021 (UTC)
Probably true, although if you want a method where you can move around within the list, insert and delete elements at the (single) moving point, and not have too much overhead from changing all the pointers around, a singly-linked zipper (pointing outwards in both directions from the finger) might be a reasonable way to go, and the list reversal algorithm more or less comes for free with that. In any case, that's all beside the main point, which is that this is still standard material on this data structure that might sometimes be useful for job applicants in particular to have seen. —David Eppstein (talk) 06:48, 23 October 2021 (UTC)

Data Type

Do linked lists definitionally only store ints? Like any ADT, you should be able to create an implementation for any data type, but the article explicitly states they are for integers. Is this just about original design, simplification, or is the article saying non-int uses are against the purpose of the structure? Sheriffjt (talk) 17:16, 30 March 2023 (UTC)

Categories: