Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Doubly Linked List

  1. Jul 19, 2004 #1
    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.
  2. jcsd
  3. Jul 19, 2004 #2


    User Avatar
    Science Advisor
    Homework Helper

    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.
  4. Jul 20, 2004 #3
    I'm using a struct.

    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.

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

    Last edited: Jul 20, 2004
  5. Jul 20, 2004 #4

    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...

  6. Jul 20, 2004 #5
    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.
  7. Jul 20, 2004 #6


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
  8. Jul 21, 2004 #7
    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.
  9. Jul 21, 2004 #8


    User Avatar
    Science Advisor
    Homework Helper

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

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

    why? What steps am I missing? I just want it to insert at the beginning.
  11. Jul 21, 2004 #10


    User Avatar
    Science Advisor
    Homework Helper

    The original head needs it's "prevNode" value reassigned, and the new head needs it's "prevNode" assigned (probably NULL).
  12. Jul 21, 2004 #11
    Thanks I got it to work in a way.
  13. Jul 23, 2004 #12

    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 :smile: 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.

  14. Jul 23, 2004 #13
    Addition to main() function

    Well if I were to give you a complete program for this problem, it would have my main function too and thats 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).
    Last edited: Jul 27, 2004
  15. Jul 25, 2004 #14
    Thanks for the tip maverick280857
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook