Talk:Linked list

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:

• 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

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)