Teuntje Teuntje - 1 month ago 8
C Question

C linked list: Placing number infront of the list and making all numbers shift

I'm trying get the method

shiftInsert
to work. I want to insert a number into the list and make the last number disappear. If this is the list
p 1 -> 2 -> 3 -> 4 -> 5
, after
shiftInsert(8)
the list needs to look like this
p 8 -> 1 -> 2 -> 3 -> 4
. As you can see the last number needs to disappear. How do I implement this?

#include <stdio.h>
#include <stdlib.h>

struct elem {
int value;
struct elem *next;
};

typedef struct elem Node;

Node *root;

Node * addElem(Node *p, int value) {
p->next = malloc(sizeof *p);
p = p->next;
p->value = value;
p->next = NULL;
return p;
}

void shiftInsert(Node *n, int v) {
int tmp;

while (n != NULL) {
Node * new_node;
new_node = malloc(sizeof (new_node));
n = n->next;
}
}

void printList() {
Node *p = root;

while (p != NULL) {
printf("%2d -> ", p->value);
p = p->next;
}

printf("NULL\n");
}

int main(int argc, char **argv) {
Node *p;
int i = 0;

root = p = malloc(sizeof (Node));
p->value = 1;

for (i = 2; i <= 10; i++) {
p = addElem(p, i);
}

printList();
shiftInsert(root, 88);
printList();
shiftInsert(root->next->next->next, 33);
printList();

return 0;
}

Answer

According to your example, you want to insert into the first position and remove the last one. So basically you want to create a new root then find the last but one element and set its next to NULL.

So first the delete function:

void deleteLast()
{
    int i, before_last = 0;
    Node *temp;

    /* Find last element to remove it*/
    temp = root;

    for(i = 0; temp->next != NULL; i++) { // "i" will be the index of the last element

        temp = temp->next;
    }

    before_last = i-1; // the one before "i" will be the new last element
    temp = root;

    for(i = 0; i < before_last; i++) { // find the one before last and set its "next" NULL
        temp = temp->next;
    }

    free(temp->next);
    temp->next = NULL;
}

New root, create an element which will be the new root. Set its next to root, then make the new element as the root.

void shiftInsertRoot(int v) {

    if (root != NULL) {
        Node * new_root;
        /* Create new root */
        new_root = malloc(sizeof (new_root));
        new_root->next = root; // save previous root
        new_root->value = v;   // set new value
        root = new_root;       // update root pointer
    }

    deleteLast();
}

According to your main, you want to insert after a certain element, you have to find it first. Then create a new element and set its next to the next of the original element, so you won't lose the rest of the list. Finally set the next of the original element to the new element.

void shiftInsertAnywhere(Node *position, int v) {
    int i;
    Node *temp;

    temp = root;

    for(i = 0; temp->value != position->value; i++) {

        temp = temp->next;
    }

    if (temp != NULL) {
        Node * new_root;
        /* Create new root */
        new_root = malloc(sizeof (new_root));
        new_root->next = temp->next; // save previous root
        new_root->value = v;   // set new value
        position->next = new_root;       // update root pointer
    }

    deleteLast();
}

This will insert after the position.

Example:

printList();
shiftInsertRoot(88);
printList();
shiftInsertRoot(33);
printList();
shiftInsertAnywhere(root->next->next, 99);
printList();
shiftInsertAnywhere(root, 17171);
printList();

Output:

enter image description here