Public Group

# Insert() function for link list

This topic is 4865 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

here is my best shot at a function that inserts a linked list into another link list at any point. it doesn't work at all and i have been racking my brains the last 24 hours trying to figure out why. all you need to know is that i have two global node pointers: node* HEAD = NULL; node* TAIL = NULL; it is a doubly linked list.
// Function : Insert
// Takes two node pointers, newNode and target, and inserts newNode into
// the list (starting at global pointer HEAD) after the target node. Keep
// in mind, newNode could be the first node of a second list, which is why the
// function traverse newNode at several places to search for its last node.

// The goal of the function is to allow for either a single node or an entire
// linked list to be inserted at any location (front, middle, end) of the main
void Insert(node* newNode,node* target)
{
node* stepNode = NULL;

// If newNode is the first node in the list.
{
// 1. Make HEAD point to first node of newNode.

// 2. Make first node of newNode point back to HEAD.

// 3. Find the last node of newNode.
stepNode = newNode;
while(stepNode->next != NULL)
stepNode = stepNode->next;
newNode = stepNode;

// 4. Make this last node point to TAIL.
newNode->next = TAIL;

// 5. Make TAIL point back to the last node.
TAIL->prev = newNode;
}

// Else if newNode is last node in list.
else if(target == TAIL->prev)
{
// 1. Establish the link between target and the first
// node of newNode.
target->next = newNode;
newNode->prev = target;

// 2. Find the last node of newNode.
stepNode = newNode;
while(stepNode->next != NULL)
stepNode = stepNode->next;
newNode = stepNode;

// 3. Link the last node of newNode and TAIL.
newNode->next = TAIL;
TAIL->prev = newNode;
}

// Else if the newNode is to be inserted at the front
// of the list.
else if(target == HEAD->next)
{
// 1. Link HEAD with the first node of newNode.

// 2. Find the last node of newNode.
stepNode = newNode;
while(stepNode->next != NULL)
stepNode = stepNode->next;
newNode = stepNode;

// 3. Link newNode with target.
newNode->next = target;
target->prev = newNode;
}

// Else, newNode is inserted somewhere in the middle of the
// list.
else
{
// 1. Link target with the first node of newNode.
target->next = newNode;
newNode->prev = target;

// 2. Find the last node of newNode.
stepNode = newNode;
while(stepNode->next != NULL)
stepNode = stepNode->next;
newNode = stepNode;

// 3. Find target's next node, prior to insertion.
node* xNode = TAIL;
while(xNode->prev != target)
xNode = xNode->prev;

// 4. Link the last node of newNode with xNode.
newNode->next = xNode;
xNode->prev = newNode;
}
}


Any suggestions rock, my fingers are raw from scratching my head.

##### Share on other sites
First, realize that the C++ standard library provides a doubly-linked list; it is called std::list, in the <list> header. Although it looks like you really are writing in C, so whatever.

Second, note that a list of n items offers n+1 places that you might want to insert a node. Special cases for the head and tail are only needed if you want to insert in front of the head, or behind the tail. And if you specify an insertion point just by a target node, you must have a clear notion of whether you want to insert "before" or "after" the target.

Third, insertion into a list will never require searching through the list for things to insert. The only pointers you need to manipulate are those of the object being inserted, and of the list nodes immediately before and after it (in the middle; whichever one of those actually exists at the end); everything else already points where it needs to.

Fourth, be aware of the order in which you assign the pointers. Oh, and don't use either pointer of the inserted item before assigning them; those pointers aren't useful (and they should be NULL, assuming a halfway sane design).

To insert "new" "after" a "target", in the middle:

First, new->prev points at target. (If there is no target, i.e. we're at beginning of list, it points NULL.)
Next, new->next points at target->next. (If there is no target, point to the old head of the list.)
Next, target->next points at new, now that we've used the value. (If there is no target, reset the head pointer accordingly.)
Finally, new->next->prev points at new. (We can't use target->next any more to fetch the object "after" new, because we already reset that pointer.)

Similarly for insertion "before"; swap nexts and prevs, but use the same order of events.

Draw it on a piece of paper with boxes and arrows if you're confused.

##### Share on other sites
What he said

But if you still need help debugging, let us know what is going wrong...losing nodes, inserting improperly, not working at all, etc. And post your most current code. or PM me. one or the other.

1. 1
Rutin
33
2. 2
3. 3
4. 4
5. 5

• 13
• 9
• 9
• 9
• 14
• ### Forum Statistics

• Total Topics
633329
• Total Posts
3011382
• ### Who's Online (See full list)

There are no registered users currently online

×