CODEWITHSUNDEEP
clinked-list
ljade
ljade

Reputation: 1

inserting in singly linked list in ascending order

Say I have a singly linked list of elements in ascending order that looks like:

A->B->D->E

I want to insert C in between B and D. I know how to point C to D, but I don't know how to point B to C since the linked list does not keep track of the prev node.

Upvotes: 0

Views: 2190

Answers (4)

Bill Lynch
Bill Lynch

Reputation: 81936

A possible implementation follows:

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

void sorted_insert(struct node **head, struct node *element) {
    // Is the linked list empty?
    if (*head == NULL) {
        element->next = NULL;
        *head = element;
        return;
    }

    // Should we insert at the head of the linked list
    if (element->value < (*head)->value) {
        element->next = *head;
        *head = element;
        return;
    }

    // Otherwise, find the last element that is smaller than this node
    struct node *needle = *head;
    while (true) {
        if (needle->next == NULL)
            break;
        if (element->value < needle->next->value)
            break;
        needle = needle->next;
    }

    // Insert the element
    element->next = needle->next;
    needle->next = element;
    return;
}

Upvotes: 1

Jason Barrett
Jason Barrett

Reputation: 239

Why not keep track of the 'previous' node as you iterate through the list? Please forgive any syntactic shortcomings, as I haven't compiled this, but this should give you the idea.

struct node {
  char name[ 10 ];
  struct node *next;
};

struct list {
  struct node *head;
};

void insert_C(struct list *list) {

  struct node *new_node = malloc(sizeof(struct node));
  if( new_node == NULL ) {
    /* Error handling */
  }

  strcpy(new_node->name, "C");

  struct node *pnode;
  struct node *prev_node = NULL;
  for( pnode = list->head; pnode->next != null; pnode = pnode->next ) {

    if( !strcmp(pnode->name, "D") ) {
      if( prev_node == NULL ) {
        /* The 'C' node is going to be the new head. */
        new_node->next = list->head;
        list->head = new_node;
      }
      else {
        prev_node->next = new_node;
        new_node->next = pnode;
      }

      break;
    } 

    /* Remember this node for the next loop iteration! */
    prev_node = pnode;
  }

}

Upvotes: 0

Dwayne Towell
Dwayne Towell

Reputation: 8593

While you are scanning down the list of nodes you have to keep two pointers: one points to the current node that you are interested in, and the other points to the previous node.

Upvotes: 1

Crowman
Crowman

Reputation: 25918

You don't need to point B to C, or to maintain a pointer to the previous element. One method is:

  1. Step to node D

  2. malloc() a new node

  3. Copy the data and next member from node D to your new node

  4. Copy the data for node C into the existing node D (which now becomes node C)

  5. Point the next member of the old node D to the new node.

For instance, excluding the possibility of inserting at the head of the list:

void insert(struct node * head, const int data, const size_t before)
{
    assert(before > 0);

    struct node * node = head;

    while ( before-- && node ) {
        node = node->next;
    }

    if ( !node ) {
        fprintf(stderr, "index out of range\n");
        exit(EXIT_FAILURE);
    }

    struct node * new_node = malloc(sizeof *new_node);
    if ( !new_node ) {
        perror("couldn't allocate memory for node");
        exit(EXIT_FAILURE);
    }

    new_node->data = node->data;
    new_node->next = node->next;

    node->next = new_node;
    node->data = data;
}

Upvotes: 0

Related Questions