How do I write insert and remove functions for a doubly linked list?

[abacus]

How would I write the insert and remove functions for a doubly linked list?

void insert(Node*& head, int i)

void remove(Node*& head, Node*& tail)

any suggestions would be appreciated. Thanks.

 

[AKG]

I'm not sure what that remove function will do. As arguments, you're only passing a pointer to the head and tail? So which node are you removing? As for insert, it would help to see a definition of your Node class. Anyways, it's quite simple. You create a new node, assign it's left and right pointers to the Nodes that should come before and after it, then change the right pointer of the node before to point to the new node, and the left pointer of the node after to point to the new node.

 

[abacus]

I'm using a struct.

struct Node {
int data;
dNode* prev;
dNode* next;
};

int main() {
int c;
Node* head = 0;

count << "Enter 5 integers: ";
for (int i = 0; i < 5; i++) {
cin >> c;
insert(head, c);
}

count << "Displaying the list: ";
print(head);

count << "Enter an integer c and c-th node will be removed: ";
cin >> c;

Node* temp = head;

for (int i = 0; i < c && temp; i++)
temp = temp -> next;

if (!temp)
count << "Many nodes aren't present.\n";
else remove(head, temp);

count << "Displaying the list: ";
print(head);

return 0;
}

Yeah I believe I made a typo for the remove function i didn't want to pass head to tail, it's head to node.

void remove(Node*& head, Node*& node)

for Insert I had this, but I'm getting errors:

dNode->next == n->next;
dNode->prev=n;
if (n->next != NULL)
n->next -> prev = dNode;

 

[maverick280857]

Hi

Here is what I would do

First, my list is called simply List. It is declared in a struct as

struct List
{
struct List *prevNode;
struct List *nextNode;
int data; // this is your info part...replace it what you want to
}

My insert function works somewhat like this

void Insert (struct List *cNode, int data)
{
// cNode points to the current node..we need to insert something
// between cNode and cNode->nextNode

struct List *newNode;
newNode = new List;
newNode.data = data;
newNode->nextNode = cNode->nextNode;
newNode->prevNode = cNode;
cNode->nextNode = newNode;
// that does it
}

void Delete(struct List *cNode)
{
// we want to delete cNode (the current node)
cNode->prevNode = cNode->nextNode;
(cNode->nextNode)->prevNode = (cNode->prevNode);
}

This comes from the algorithms we made in school while learning C++ and I am not sure if it is what you're looking for. (If the abovementioned code is wrong, please let me know...its been quite a while since I did this though I think it should work.)

Hope that helps...

Cheers
Vivek

 

[Brianjw]

What mav wrote is pretty correct. However in my experience there are different insert/remove methods that must be used depending on the situation.

When inserting it is best to check first if the list is empty, if so you then do one insert where the head becomes the new node you're trying to create and the head points to null at prev and next. If its not empty you can get creative here. Do you want to insert at the top of the list, as in each node you insert becomes the head or at the bottom of the list, each node you insert becomes the tail.

Removing is where you have to be extra careful, you have to check for null pointers when removing, because if you try to remove something at the end of a list you can get a run time error because you're trying to make a null node point to something, which just makes it unhappy.

Inserting will have 3 different insert methods, is it the first node, is it not the first but becoming the head? or is it becoming the tail? Inserting in the center is an optional fourth way to do it which is a bit easier cause of no nulls to think about but may not be what you need.

So for removing you'll have 3 different methods, is it a node at one of th ends of the list, is it somewhere in the middle, and is it the last node.

Of course some of this can be eliminated if you make a doubly linked ring list but the insert gets a bit more creative and the remove can be cut down a bit.

Looking at your code vs. Mavs code mav did also make the correction that the struct you're using for the list has to refer to itself for the prev/next but are never instantiated until they're used. Hence they're null.

Hope this helps a bit.

 

[Hurkyl]

In any case, IMHO it is far more important to figure out what you need to do in terms of diagrams before you do it in code. Try to draw out how the list looks at the beginning and end of the operation, and understand the individual steps to get from one to the other.

 

[abacus]

Thanks mav and brian,

So far I got the insert to work I believe.


void insert(cNode*& head, int n) {
cNode *newNode;
newNode = new cNode;
newNode->data = n;
newNode->next = head;
head = newNode;
}


The remove function is a bit tricky since I want whatever I input as my c-th node to be removed.

 

[NateTG]

Generally it's better to pass a pointer to the data structure

void insert(cNode*& head, int n) {
cNode *newNode;
newNode = new cNode;
newNode->data = n;
newNode->next = head;
head = newNode;
}

If this is a doubly-linked list, then you need to do some other stuff as well. Otherwise, you will corrupt the list.

 

[abacus]

If this is a doubly-linked list, then you need to do some other stuff as well. Otherwise, you will corrupt the list.

why? What steps am I missing? I just want it to insert at the beginning.

 

[AKG]

why? What steps am I missing? I just want it to insert at the beginning.

The original head needs it's "prevNode" value reassigned, and the new head needs it's "prevNode" assigned (probably NULL).

 

[abacus]

Thanks I got it to work in a way.

 

[maverick280857]

Hello

I should've passed a pointer. This unfortunately came from my very first doubly linked list program, before our instructor "allowed" us to use pointers Change that and the method will work. But you will still have to (if you use my code exactly) include some extra code for insertion right at the top of the list. Thats an exception you have to take care of since there are two pointer nodes on either end that you have to take care of...its a doubly linked list after all :-D.

EDIT: You can improve this and make it better...this was just an elemantary starting point.

Cheers
Vivek

 

[maverick280857]

Addition to main() function

Looking at your code vs. Mavs code mav did also make the correction that the struct you're using for the list has to refer to itself for the prev/next but are never instantiated until they're used. Hence they're null.

Well if I were to give you a complete program for this problem, it would have my main function too and that's where we would've instantiated them to null...

// this goes into main
struct List *hNode = new List,
*cNode = hNode;
cNode->prevNode = NULL;

Alternatively if you make a class for your list, this should go into a user-defined and/or paramatetrized constructor. (I think after this, some basic pointer problems will be resolved too. I faced a lot of them while working on different computers though all having the same configuration and running Windows 98. There seemed to be something wrong with the Turbo C++ compiler sharing memory with Windows or transacting with the OS kernel for on some computers, it was a breeze to do new and delete without silly pointer errors).

 

[abacus]

Thanks for the tip maverick280857