Inserting number into a sorted doubly linked list?

Question

Hey there, I'm given a doubly linked list, lets just say this is it

list>15<->25<->33<->45

And I have to add 40 to this list. I just need the algorithm in pseudocode. If anyone can help, thanks.

Answer 1

Do you have a null node as the root? If you do then this avoids having to take care of the fencepost problem.



I'll assume you don't, that you are just looking @ each node:



Look @ the first node: if it's greater than the new number then just insert at the beginning of the list.



Otherwise go through the list until you find the end of the list or the next number is greater than the new number.



Here is some pseudocode:



if(new < node){

insertInFront;

}else{

while(!endOfList && new > node){

++node;

}

if(endOfList){

insertAfter node

}else{

node.previouse = new

new.next = node

}



Here is an example of inserting 40 into your list:



(40 < 15) = false

--> enter loop, increment node



(40 < 25) = false

incrementNode



(40 < 33) = false

incrementNode



(40 < 45) = true

insert

45.previous = 33

33 -> 40

40 -> 45



New list looks like this:



15 <-> 25 <-> 33 <-> 40 <-> 45



Here is the first fencepost: insert 8:



(8 < 15) = true

insert @ front:



8 <-> 15 ...

(notice you CANNOT do what you did before because there is no previous node that 15 pointed to, but if you had a null node then this would have not been different):



2nd fencepost: insert 60



60 < 15 = false

incrementNode



60 < 25 = false

incrementNode



60 < 33 = false

incrementNode



60 < 45 = false

end of list reached, insert @ end



... 33 <-> 45 <-> 60



Again, unless 45 points to a sentinel node, this cannot be handled "normally".

Answer 2

Sort Doubly Linked List

Answer 3

Start with the first node

Compare the data in the node (15) with your number (40)

Since it's less than your number, keep going; you can use a loop for this, e.g.:

While NextNode.Data < NewData

NextNode = NextNode.Next



Then, you insert it...

NewNode.Data = NewData

NextNode.Prev.Next = NewNode

NewNode.Prev = NextNode.Prev

NewNode.Next = NextNode

NextNode.Prev = NewNode



Or something like that.

Answer 4

Start at the first node. Walk the list until you pass the right spot (it would be after you pass 33 and get to 45). Point your new item's last pointer to 33 and its next pointer to 45. Point 45's last pointer, and 33's next pointer, to your new node.

Answer 5

int SortByName(AddressPtr_t Cur) { // the midsection loop technology pointer AddressPtr_t Iter = Cur; // A boolean fee for remembering no rely if // the record became changed or no longer bool replaced; //Get to the commencing up lower back whilst (Cur && Cur->Prev) Cur = Cur->Prev; // start up the type // If there exists an element, Iter is the // next element if (Iter) Iter->next; // extremely keeps iterating until there // are no longer any ameliorations and Cur = NULL whilst (replaced || Cur) { // Reset the changed swap for this technology replaced = fake; whilst (Iter) { // If it belongs until now Cur, positioned it there if (strcmp(Cur->call,Iter->call) > 0) { // do away with Iter from its region if (Iter->next) Iter->next->Prev = Iter->Prev; Iter->Prev->next = Iter->next; // Insert Iter until now Cur Iter->Prev = Cur->Prev; if (Iter->Prev) Iter->Prev->next = Iter; Iter->next = Cur; Cur->Prev = Iter; // Set changed flag replaced = genuine; } // next technology Iter = Iter->next; } if (replaced) { // start up sorting from the commencing up lower back // Get to the commencing up lower back whilst (Cur && Cur->Prev) Cur = Cur->Prev; // If an element exists, Iter is the // next element if (Cur) Iter = Cur->next; } else { // bypass to the subsequent fee if (Cur) Cur = Cur->next; if (Cur) Iter = Cur->next; } } return 0; }