Talk:Doubly linked list

Code needs source or must be removed

Who wrote this code? Where did it come from? Andrevan@ 22:14, 27 September 2013 (UTC)

Indeed the C source code is not appropriate for Wikipedia. It isn't even good source code. It entirely misses the point of having two-way links, namely that nodes can be added or deleted at known locations in constant time. Those features are described better in the pseudocode section and any decent programmer could turn them into C in a flash. C code gone. McKay (talk) 05:03, 17 September 2015 (UTC)

I see this is already covered in Talk. I had to remove the nonsense again. If you have this page on your watch lists, please watch it for a few days. Whoever the code author is wants to keep re-adding it. -- 107.50.75.83 (talk) 16:59, 15 March 2016 (UTC)

The C code is terrible and having it here is embarrassing. Deleting it again. McKay (talk) 04:08, 10 January 2017 (UTC)

Bug in Ada code?

I don't think insertBefore and insertAfter are correct. If you insert into the beginning of the list, firstNode->prev is not null, and if you insert at the end of the list, lastNode->next is not null.

I think the code should look like this:

 function insertAfter(List list, Node node, Node newNode)
    newNode.prev  := node      
    if node.next == null
        list.lastNode  := newNode
    else
        node.next.prev  := newNode
    newNode.next  := node.next
    node.next  := newNode

 function insertBefore(List list, Node node, Node newNode)
    newNode.next  := node
    if node.prev == null
        list.firstNode  := newNode
    else
        node.prev.next  := newNode
    newNode.prev  := node.prev
    node.prev  := newNode

— Preceding unsigned comment added by 195.159.207.66 (talk) 17:20, 30 January 2017 (UTC)

I changed the code so that people won't get into the same trap as me when using this code. 195.159.207.66 (talk) 14:01, 31 January 2017 (UTC)

I'll guess at the source of this problem, which shows a major deficiency in this article. Usually doubly-linked lists are not implemented with a NULL pointer at the end, but with an extra node that holds no data. That is mentioned in the lead where it is called a sentinel node (but I see header node much more often). After the lead, it is forgotten. An empty list then consists of just the header node pointing forwards and backwards to itself. Implemented this way, all of the basic operations become simpler, without any need to test for the beginning or end of the list. I suspect the Ada procedure was written for that implementation. McKay (talk) 01:24, 3 February 2017 (UTC)

Yes, but it's nice to avoid having a sentinel node if you don't use separate node objects that links to the actual data, i.e. when both data and the next/prev links are stored in the same object. 195.159.207.66 (talk)

In Ada you may define a constrained record type with variant part that specifies alternative lists of components. It takes a bit more memory for storing a variant, but eliminates unwanted creation of stored object and need for sentinel object's value. — Preceding unsigned comment added by 176.59.37.220 (talk) 05:20, 8 September 2017 (UTC)

The article said that the concept of doubly linked list is also the basis for the mnemonic link system. Clearly, it is not. Mnemonics use simple bijections: digit --> picture --> digit. A direct translation back and forth from thing to remember to mnemonic back to thing to remember. Not at all like a linked list; a linked list is like a chain. — Preceding unsigned comment added by Khoitsma (talk • contribs) 21:12, 29 August 2018 (UTC)