C++

Forum

 
Linked List insert

SSDEEZ (33)
I'm trying to make an insert function for a linked list.

It needs to insert at the end of the list and not traverse if the head node is the only node in the list.

if the function receives an "i" that is the same as the index (data) of one of the nodes then it needs to move the node that is already in the list to the end of the list.

This is what I have so far and I'm wondering why this initial while loop doesn't do the unlinking and relinking I need it to.

Any conducive thoughts that can use this already laid out logic would be greatly appreciated!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 

void list::insert(int i){

	node *tracker = head;
	
	while(tracker->next != NULL){
		tracker = tracker->next;
		if(tracker->index == i){
			(tracker->prev)->next = tracker->next;
			break;
		}
	}

	
	if(head->next == NULL){
		node*newNode = new node;
		newNode->index = i;
		newNode->next = NULL;

		head->next = newNode;
		newNode->prev = head;
		newNode->next = NULL;
		numNodes = numNodes + 1;
		return;
	}

	else{
		node*newNode = new node;
		newNode->index = i;
		newNode->next = NULL;
		node *last = head;

		while(last->next != NULL){
			last = last->next;
		}
		last->next = newNode;
		newNode->prev = last;
		numNodes = numNodes + 1;
	}


}
DizzyDon (121)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
struct node {
    int   index;
    node *next, *prev;

    node(int i, node* n = nullptr, node* p = nullptr)
        : index(i), next(n), prev(p) { }
};

void list::insert(int i) {
    // Set n to last node in list, or nullptr if list is empty.
    // Set x to first matching node found, or nullptr if no match.
    node* n = head, *x = nullptr;
    if (n) {
        for ( ; n->next; n = n->next) if (!x && n->index == i) x = n;
        if (!x && n->index == i) x = n;
    }

    // If a matching node was found, remove it from the list.
    if (x) {
        if (!x->next) return; // already at end of list
        if (x->prev)
            x->prev->next = x->next;
        else
            head = x->next;
        x->next->prev = x->prev;
        x->next = nullptr;
    }
    // If no matching node was found, create a new node.
    else {
        x = new node(i);
        ++numNodes;
    }

    // Add the node to the end of the list.
    if (n) n->next = x;
    else   head    = x;
    x->prev = n;
}

Last edited on
seeplus (6591)
If you need to insert at the end of a list, then it's common to also have a tail pointer as well as a head pointer - especially with a double-linked list (prev, next).
Last edited on
Topic archived. No new replies allowed.