Double Linked List insert not arranging in order

[kingkush]

I am writing a program to create a linked list or chars and have them places in ascending order but I can;t seem to get it to into ascending order. It seems all jumbled up and i cant figure out where I am messing up. Here is the insert function:

int DCList::insert(char c)
{
    std::cout << "Insert Function. Inserting: " << c << std::endl;
    Node* cur = head;
    //Create new Node
    Node* newNode = new Node;
    newNode->c = c;
    newNode->next = nullptr;
    newNode->prev = nullptr;
    if(head == nullptr)
    {
        head = newNode;
        newNode->next = head;
        newNode->prev = nullptr;
        tail = newNode;
        std::cout << "Success inserting: " << c << std::endl;
        return 0;
    }
    else
    {
        //check tail first?
        if(newNode->c > tail->c)
        {
            tail->next = newNode;
            newNode->prev = tail;
            newNode->next = head;
            tail = newNode;
            if(newNode->c == tail->c)
            {
                std::cout << "Success Inserting: " << newNode->c << std::endl;
                return 0;
            }
            else
            {
                std::cout << "Fail Inserting: " << newNode->c << std::endl;
                return -1;
            }
        }
        if(newNode->c < cur->c)
        {
            head = newNode;
            cur->prev = newNode;
            newNode->next = cur;
            newNode->prev = nullptr;
            if(cur->next == nullptr)
            {
                cur->next = head;
            }
            //tail = cur; //needed?
            std::cout << "Success" << std::endl;
            return 0;
        }
        else
        {
            while(newNode->c < cur->c)
            {
                cur = cur->next;
            }
            Node* nextNode = cur->next;
            nextNode->prev = newNode;
            newNode->prev = cur;
            newNode->next = nextNode;
            cur->next = newNode;
            return 0;
        }
    }
}

Output:

a d e b c f 

[jonnin]

I don't see the error, but it looks like too many cases.

you need empty: insert and

while (newthing <= current)
current = next
insert here
if here was tail, update tail.

I can see that jumping to tail to insert after it for efficiency, but that is just a tweak, not part of the core algorithm.

[kingkush]

I rewrote the section that checked tail first and placed it after my last while loop but still got the same issue. I believe my error is in the last else statement because the first and last nodes look like they get implemented properly because A (or whatever is smaller) is always first and F (or whatever is greater) is always last.

[Enoizat]

if(newNode->c < cur->c)
{
    ...
}
else
{
    while(newNode->c < cur->c)
    {
        ...
}

Am I misunderstanding your code or is it possible that you never get inside that while condition?

[jonnin]

the while seems wrong.
say you have a list of 1,3,5,7 and get 4.
its not empty, it doesnt go after tail, and its not in front of head.
4 isnt less than 1, so the while loop is skipped.
then it inserts in a weird place...

Do you agree?

[dhayden]

It looks like you have tail->next == head, but head->prev == nullptr. Is that your intention? I guess it's okay, but it's unconventional.

Line 45. Wait... if tail->next == head then no node's next pointer will ever be NULL.

So the question is what should tail->next point to? Figure that out and then fix the code so it's consistent.

[kingkush]

@Enoizat yes thats correct. I meant it to be > instead because i test the < condition before.

@jonin yes i do agree thats whats happening. After changing the above mentioned code I'm getting this output after inserting abcfed (in that order).

a b c f

It appears e and d fail to get inserted.

@dhayden Yes. That was my intention. I only want the first Node's prev = nullptr. I encountered the error of not having any nodes point to prev so i need to fix that.



To clarify it's actually a doubly linked circular linked list where the last node point to the first node (or head)

[dhayden]

Here's code that works. The biggest problem was that you were inserting after "cur" when you should have inserted before.

#include <iostream>

class DCList {
private:
    class Node
    {
      public:
	Node * prev, *next;
	char c;
    };
    // head->prev == nullptr. tail->next == head
    Node *head, *tail;

public:
    DCList():head(nullptr), tail(nullptr) {  }
    void print(std::ostream &os);
    int insert(char c);
};

int
DCList::insert(char c)
{
    std::cout << "Insert Function. Inserting: " << c << std::endl;
    //Create new Node
    Node *newNode = new Node;
    newNode->c = c;
    newNode->next = nullptr;
    newNode->prev = nullptr;

    if (head == nullptr) {
	head = newNode;
	newNode->next = head;
	newNode->prev = nullptr;
	tail = newNode;
	std::cout << "Success inserting: " << c << std::endl;
	return 0;
    } else {
	if (newNode->c >= tail->c) { // insert at tail
	    tail->next = newNode;
	    newNode->prev = tail;
	    newNode->next = head;
	    tail = newNode;
	} else {
	    // Insert before tail
	    Node *cur = head;
	    while (newNode->c > cur->c && cur->next != head) {
		cur = cur->next;
	    }
	    // dmh: old code inserted after cur

	    newNode->prev = cur->prev;
	    newNode->next = cur;
	    if (cur == head) {
		head = newNode;
	    } else {
		cur->prev->next = newNode;
	    }
	    cur->prev = newNode;
	}
    }
    return 0;
}

void
DCList::print(std::ostream &os)
{
    bool didHead=false;
    for (Node *cur = head; cur && (cur != head || !didHead); cur = cur->next) {
	os << cur->c << ' ';
	didHead = true;
    }
}


int
main()
{
    DCList lst;
    lst.insert('b');
    lst.insert('c');
    lst.insert('d');
    lst.insert('e');
    lst.insert('a');
    lst.insert('f');

    lst.print(std::cout);
    std::cout << '\n';
}

But look at how awkward the print() method is. This is entirely due to having the list be circular. Both print and insert can be simplified:

int
DCList::insert(char c)
{
    std::cout << "Insert Function. Inserting: " << c << std::endl;
    //Create new Node
    Node *newNode = new Node;
    newNode->c = c;
    newNode->next = nullptr;
    newNode->prev = nullptr;

    // Set "after" to the node that be after the new one, or NULL
    // if the new node goes at the end
    Node *after;
    for (after = head; after ;after = after->next) {
	if (newNode->c < after->c) {
	    break;
	}
    }
    // Link it in
    newNode->next = after;
    if (after) {
	newNode->prev = after->prev;
	after->prev = newNode;
    } else {
	newNode->prev = tail;
	tail = newNode;
    }
    if (newNode->prev) {
	newNode->prev->next = newNode;
    } else {
	head = newNode;
    }
    return 0;
}

void
DCList::print(std::ostream &os)
{
    for (Node *cur = head; cur; cur = cur->next) {
	os << cur->c << ' ';
    }
}