Doubly Linked List Implementation with Pointers C++

Question

I am currently teaching myself C++ and am attempting to implement a doubly-linked list in C++ using pointers which is partially complete. I am aware that the code currently fails to deal with dangling nodes or output errors, both of which I will implement next. However, the code should atleast be able to construct a list object and add elements to it. Currently, I am getting an error when I attempt to call a constructor for the list, which says that I am requesting a conversion from LinkedList* to non scalar type LinkedList. Why is my list being declared as a pointer? Any help would be much appreciated, thank you!

LinkedList.h
#ifndef LINKEDLIST_H
#define LINKEDLIST_H

struct dataElement {
  int key;
  int id;
};

struct Node
{
    dataElement data;
    Node* next;
    Node* prev;
};


class LinkedList
{
public:
    /** Default constructor */
    LinkedList();
    /** Default destructor */
    virtual ~LinkedList();
    void addAtFront(int newElement);
    void addAtBack(int newElement);
    int removeTop();
    int removeBottom();
    int getTop();
    int getBottom();
    int findKey(int keyToFind);
protected:
private:
    Node* head;
    Node* tail;
    int size;
};

#endif // LINKEDLIST_H


LinkedList.cpp
#include "LinkedList.h"
#include <iostream>
#include <stdlib.h>


LinkedList::LinkedList()
{
size = 0;
}

LinkedList::~LinkedList()
{
//dtor
}

void LinkedList::addAtFront(int newElement)
{
if (size == 0)
{
    Node temp;
    temp.data.id = newElement;
    temp.data.key = 0;
    head = &temp;
    tail = &temp;
    ++size;
}
else
{
    Node temp;
    temp.data.id = newElement;
    temp.data.key = size;
    temp.next = head;
    head->prev = &temp;
    head = &temp;
    ++size;
}
}

void LinkedList::addAtBack(int newElement)
{
if (size == 0)
{
    Node temp;
    temp.data.id = newElement;
    temp.data.key = 0;
    head = &temp;
    tail = &temp;
    ++size;
}
else
{
    Node temp;
    temp.data.id = newElement;
    temp.data.key = 0;
    tail->next = &temp;
    temp.prev = tail;
    tail = &temp;
    ++size;
}
}

LinkedListTest.cpp
#include "LinkedListTest.h"
#include "LinkedList.h"

int main()
{
LinkedList list = new LinkedList();
list.addAtFront(0);
}

when dealing with pointers, you need to use `->` instead of `.` to get to member functions. Make that last line of main `list->addAtFront(0);` and see what happens. — Charlie, Oct 21 '13 at 00:31

score 5 · Accepted Answer · answered Oct 21 '13 at 00:33

The error means that somewhere you have a LinkedList list declared not as a pointer, to which you assign a new LinkedList() which is of type LinkedList* (and not LinkedList). It should be:

LinkedList* list = new LinkedList(); // I declare a pointer to a list
list->addAtFront(0); // I call a method on a pointer to an object

or

LinkedList list;
list.addAtFront(0);

They are two different types which are allocated in two different storages and this is important, keep reading.

What I see more importantly is that when you use dynamically allocated memory you should take case of actually allocate on heap objects that should persist the scope in which they are declared.

More specifically, this:

{
  Node temp;
  ..
  head = &temp;
  ..
}

This will cause problems because temp is declared as automatic storage on stack, which means that once you obtained its address and assign it to head or tail or whatever, that address won't be valid anymore once the scope exited. You should allocate it on heap:

Node temp = new Node(value, id);
head = temp;
tail = temp;
++size;

Mind that this requires that you clean up memory by yourself from the heap when the Node is not needed anymore.

This means that I need to declare the node outside of the addElement methods correct? If so, do I need to treat it like an array and declare, say, 10 initial nodes and expand the list as it becomes necessary? I guess I could just use the add element methods to move the front and tail pointers accordingly. This just seems somewhat inefficient. — Alex Barry, Oct 21 '13 at 01:06
No, incorrect. You declare them inside `addElement` but through `new` operator. This will allocate the memory for the list element on the heap instead that locally to the stack. Take a read here: http://stackoverflow.com/questions/79923/what-and-where-are-the-stack-and-heap — Jack, Oct 21 '13 at 01:27

score 1 · Answer 2 · answered Oct 21 '13 at 00:30

1

new returns a pointer to a LinkedList object, which you are attempting to assign to a LinkedList object, instead of a pointer.

LinkedList list = new LinkedList();

should read

LinkedList list;

answered Oct 21 '13 at 00:30

Alex P

530
1
6
13

score 1 · Answer 3 · answered Sep 22 '14 at 23:43

Try this completely implemented doubly linked list:

#include <stdio.h>

struct node{
int data;
struct node *next,*prev;
};

struct node *head=NULL;

void insert(int data, int position)
{
    struct node *newNode=malloc(sizeof(struct node));
    newNode->data=data;

    if(position<1)
    {
      printf("Invalid Insertion Position \n");
      return;
    }
    if(head==NULL && position==1)
    {
        newNode->next=NULL;
        newNode->prev=NULL;
        head=newNode;
    }
    else if(head==NULL && position!=1)
    {
        printf("Invalid Insertion Position \n");
    }
    else if(position==1)
    {
        newNode->next=head;
        newNode->prev=NULL;
        if(head->next!=NULL)
        {
           head->next->prev=newNode;
        }
        head=newNode;
    }
    else
    {
        int i=0;
        struct node *temp=head;
        while(temp->next!=NULL && i<position-2)
        {
            i++;
            temp=temp->next;
        }
        if(i<position-2)
        {
            printf("Invalid Insertion Position \n");
        }
        else
        {
        newNode->next=temp->next;
        temp->next=newNode;
        newNode->prev=temp;
        if(temp->next!=NULL)
        {
            temp->next->prev=newNode;
        }
        }

    }
}

void delete(int position)
{
    int i=0;
    if(position<1)
    {
        printf("Invalid Position of Deletion \n");
        return;
    }
    if(head==NULL)
    {
        return;
    }
    if(position==1)
    {
        head=head->next;
        if(head!=NULL)
        {
        head->prev=NULL;
        }
    }
    else
    {
        struct node *temp=head;
        while(temp->next->next!=NULL && i<position-2)
        {
            i++;
            temp=temp->next;
        }
         if(i<position-2)
            {
                printf("Invalid Position of Deletion \n");
                return;
            }
        else
            {
                temp->next=temp->next->next;
                if(temp->next!=NULL)
                temp->next->prev=temp;
            }
    }
}



void printlist()
{
    if(head==NULL)
    {
        printf("Empty List!! \n");
        return;
    }
    struct node *temp=head;

    while(temp!=NULL)
    {
        printf("%d",temp->data);
        printf("\t");
        temp=temp->next;
    }
    printf("\n");
}

int main()
{
    int t;
    printf("Enter number of Test Cases: \t");
    scanf("%d", &t);
    printf("\nEnter Queries in this format: \n");
    printf("For Insertion: \t I data position \n");
    printf("\tEx:\t I 25 5 \n");
    printf("For Deletion: \t D position \n");
    printf("\tEx:\t D 2 \n\n");

    while(t--)
    {
        char c;
        int a,b;
        printf("Enter query: \t");
        scanf("%c", &c);
        scanf("%c", &c);

        if(c=='I')
        {
            scanf("%d %d", &a,&b);
            insert(a,b);
        }
        else if(c=='D')
        {
           scanf("%d", &a);
           delete(a);
        }
        printlist();
    }

}

score 1 · Answer 4 · edited Sep 29 '16 at 06:35

I think you should implement two classes:

Doubly linked lists with a sentinel: Double_sentinel_list, and
Doubly linked nodes: Double_node.

Member Variables. Constuctors,Destructors:

int size() const; 
  //Returns the number of items in the list.
bool empty() const;  
  // Returns true if the list is empty, false otherwise.
Type front() const;  
  // Retrieves the object stored in the node pointed to by the next pointer of the head sentinel. This function throws a underflow if the list is empty. 
Type back() const;   
  // Retrieves the object stored in the node pointed to by the previous pointer of the tail sentinel. This function throws a underflow if the list is empty.
Double_node<Type> *head() const;  
  // Returns the head pointer.
Double_node<Type> *tail() const;  
  // Returns the tail pointer.
int count( Type const & ) const;  
  // Returns the number of nodes in the linked list storing a value equal to the argument. Mutators

This class has seven mutators:

void swap( Double_sentinel_list & );  
  // The swap function swaps all the member variables of this linked list with those of the argument.
Double_sentinel_list &operator=( Double_sentinel_list & );  
  // The assignment operator makes a copy of the argument and then swaps the member variables of this node doubly linked sentinel list those of the copy.
void push_front( Type const & );  
  // Creates a new Double_node<Type> storing the argument, the next pointer of which is set to the next pointer of the sentinel and the previous pointer is set to point to the sentinel. Theprevious pointer of what was the first node is set to the new node.
void push_back( Type const & );  
  //  Similar to push_front, this places a new node at the back of the list.
Type pop_front();  
  // Delete the first non-sentinel node at the front of the linked list and the previous and next pointers of any other node (including the sentinels) within the list. Return the object stored in the node being popped. Throw an underflow exception if the list is empty.
Type pop_back();  
  // Similar to pop_front, delete the last non-sentinel node in the list. This function throws a underflow if the list is empty.
int erase( Type const & );  
  // Delete the first node (from the front and other than the sentinals) in the linked list that contains the object equal to the argument (use == to to test for equality with the retrieved element). Update the previous and next pointers of any other node (including possibly the sentinels) within the list. Return the number of nodes that were deleted.

score 0 · Answer 5 · answered Oct 21 '13 at 00:30

0

Either

LinkedList list;
list.addAtFront(0);

or

LinkedList* list = new LinkedList();
list->addAtFront(0);
delete list;

answered Oct 21 '13 at 00:30

Igor Tandetnik

50,461
4
56
85

Doubly Linked List Implementation with Pointers C++

5 Answers5

Linked