How can a node be inserted in the middle of a linked list?

Answer 1

when you have two nodes and when you want to insert the third node between the 1 & 2 then, store the address of the third in the next pointer of 1st and address of 2nd in the next pointer of 3rd.

by kochu

Answer 2

It depends whether the list is singly-linked or doubly-linked. Let's examine the case for singly-linked lists, which are much easier to implement. Some sample code is included at the end of this article.

Before we can make an insertion, we must first locate the insertion point. We do this by traversing the list from the head node, comparing the current node's data with the data we want to add. If it is less than or equal to the current node's data, then we've located the insert point. Otherwise we move to the next node and compare the data again, and repeat until the insert point is found. If there is no next node, then we simply add the new node to the end of the list.

So far so simple. But there is a problem. In order to insert a new node before an existing node (the insert point), we must update the node that currently comes before the existing node; the new node will become that node's next node. However we can only traverse a singly-linked list in one direction, we cannot go back to a previous node without traversing the list again.

There are several solutions to the problem. We could allow the list to handle the traversal, maintaining pointers to previous nodes as required. However, while it is natural to assume that because the list manages the nodes it contains it should also be responsible for the insertion of new nodes within the list, this is not the case at all. The only node the list actually knows anything about is the head node, and that is its sole responsibility; to maintain the head node pointer, creating it if necessary, but nothing more and nothing less.

The nodes themselves are solely responsible for their own data and for maintaining their next pointers, but because of this they are in a far better position to determine where new data should be inserted, and how to insert it. It either comes before them or it comes after them. So we should let the nodes pass new data amongst them and let them sort out where it should actually be inserted, adjusting their own pointers as required.

Once the head node has been created, further insertions can be passed directly to the head node itself, via its own Insert() method. The return value then becomes the new head node for the list (which will either be the same node or a new node altogether). In effect, the current head node tells the list which node is now the head node!

Whenever a node's Insert() method is called, the data that is passed to it is compared with the node's own data to decide if the data should come before or after that node.

If the given data is greater, control of the data passes to the next node and the return value becomes the next node. In other words, the next node informs its previous node what its next node should really be!

However, if the next node is currently NULL, then this node must be the last node. In that case, a new node is created which then becomes this node's next node. The new node is now the last node so its next pointer is set to NULL.

In either of these cases, the method will return a pointer to itself. If the call came from the list, then this node is still the head node. And if the call came from the previous node, then this node remains its next node.

However, if the given data is less than or equal to the node's own data, then it must come before this node. In that case, a new node is created, it's next node is set to this node and the new node is returned. If the call came from the list, then the new node becomes the new head node, otherwise the new node becomes the previous node's next node.

In effect, the node pointers take care of themselves and the nodes decide amongst themselves where data is to be inserted, the only exception being the initial head node which is taken care of by the list itself. Everything as it should be.

// Purpose: Singly-linked list node insertion demo.

// DISCLAIMER: Use at your own risk!

#include <iostream>

// A (very) simple data class to put into the list.

class Data

{

public:

Data(int i):m_iValue(i){}

void Report()const{ std::cout << m_iValue << std::endl; }

bool operator> (const Data & theData){ return( m_iValue > theData.m_iValue ); }

private:

int m_iValue;

};

// The node class.

class Node

{

public:

Node(Data & theData, Node * nextNode):

m_pData(&theData),

m_pNext(nextNode){}

~Node(){if(m_pNext)delete(m_pNext); delete(m_pData);}

Node * Insert(Data & theData);

void Report()const{m_pData->Report(); if(m_pNext) m_pNext->Report();}

private:

Data * m_pData;

Node * m_pNext;

};

Node * Node::Insert(Data & theData)

{

if(theData > *m_pData)

{

if( m_pNext )

m_pNext = m_pNext->Insert(theData);

else

m_pNext = new Node(theData, NULL);

return( this );

}

return( new Node(theData, this));

}

class List

{

public:

List():m_pHead( NULL ){}

~List(){delete(m_pHead);}

void Insert(Data & theData);

void Report(){if(m_pHead) m_pHead->Report();}

private:

Node * m_pHead;

};

void List::Insert(Data & theData)

{

if( m_pHead )

m_pHead = m_pHead->Insert(theData);

else

m_pHead = new Node(theData, NULL);

};

int main(int argc, char* argv[])

{

int iData;

Data * pData;

List LinkedList;

for(;;)

{

std::cout << "Enter a value (0 to quit): ";

std::cin >> iData;

if(!iData)

break;

pData=new Data(iData);

LinkedList.Insert(*pData);

}

LinkedList.Report();

return(0);

}

Answer 3

void insertNode(struct linked_list *list, const int i, const int data) {

if( list 0 ) {

// create new node

struct linked_list_node *newNode = createLinkedListNode(data);

newNode->next = list->root;

list->root = newNode;

++(list->size);

return;

}

struct linked_list_node *current = list->root;

int currentIndex;

// move to list[i]

for(currentIndex = 0; currentIndex < i; ++currentIndex) {

current = current->next;

}

// create new node

struct linked_list_node *newNode = createLinkedListNode(data);

newNode->next = current->next;

current->next = newNode;

++(list->size);

}

Read more: http://wiki.answers.com/How_to_create_a_single_link_list_in_c#ixzz19Pm5odyF

Answer 4

As each implementation is different (assuming you meant a circular singly-linked list) the general algorithm is:

1. Create a new node, making sure it is not allocated locally in the function and thus will not be destroyed when the function execution finishes
2. Fill in data
3. Use the "last node" pointer in the list and copy the "next" pointer location (pointing to the first node) into the new nodes "next" pointer
4. Set the "last node" "next" pointer to point to the new node
5. Change the list's "last node" pointer to point to the new node

This should illustrate the algorithm:

struct list_node {

struct data data;

struct list_node *next;

}

struct list {

struct list_node *last;

}

void push(struct list *list, struct data *data){

struct list_node *new_node = (struct list_node*)malloc(sizeof(struct list_node));

new_node->data = *data;

new_node->next = list->last_node->next;

list->last_node->next = new_node;

list->last_node = new_node;

}

Answer 5

Queues are distinct in that extractions occur at the head while insertions occur at the tail. A standard singly-linked list only maintains a pointer to the head node which means you must traverse the entire list to get to the tail for an insertion. However, with a minor modification, you can add another pointer that points to the tail node, without going to the expense of a doubly-linked list. This then gives constant time access to both the head and the tail, which is essential in a queue.

To insert a new element, you create a node for it, then set the current tail's next node to the new node, then set the tail to the new node. If there is currently no tail, then the list is empty so the new node simply becomes the tail (as well as the head).

To extract an element, make sure there is a non-zero head first. If so, use a temporary pointer to refer to it, then extract its element. Set the head to the temp pointer's next node then destroy the temp pointer. Finally, return the extracted element.

Answer 6

To insert a node into a doubly linked list, create the following function. The function accepts 4 arguments, a pointer to the list, a pointer to the (new) node, and the nodes that will come before and after it once inserted. If the previous node is NULL, the new node becomes the head of the list. If the next node is NULL, the new node becomes the tail of the list.

Node* insert (List* list, Node* node, Node* prev, Node* next) {

if (!list !node) return 0;

node->next = next;

node->prev = prev;

if (!prev)

list->head = node;

else

prev->next = node;

if (!next)

list->tail = node;

else

next->prev = node;

return node;

}

With this function in place, you can simplify calls to it by creating the following helper functions:

Node* insert_before (List* list, Node* node, Node* next) {

if (!next)

return insert (list, node, list->tail, 0);

else

return insert (list, mode, next->prev, next);

}

Node* insert_after (List* list, Node* node, Node* prev) {

if (!prev)

return insert (list, node, 0, list->head);

else

return insert (list, mode, prev, prev->next);

}

Answer 7

A singly linked list acts as a dynamically implemented stack in that insertion and deletion take place only from the top.

Answer 8

first :node b is to be inserted between node a and node c, after nodeb->next=nodea->next;

nodeb>prev=nodea;

nodea->next=nodec;

nodec->prev=nodeb