CODEWITHSUNDEEP
c++pointerslinked-listsegmentation-faultdoubly-linked-list
Manu Kolehmainen
Manu Kolehmainen

Reputation: 29

Creating LinkedList exits with return code -11 (SIGSEGV)

So I'm trying to create a Linked List class to understand better how pointers and data structures work but I keep running into a -11 SIGSEGV error. When I looked up the error it said that I might be using dereferenced pointers or accessing an array out of its bounds but neither of those makes sense for my program. I've searched everywhere for similar issues but none of them seem to apply to my program. Can anyone else see what I'm doing wrong?

#include <stdexcept>
#pragma once
using namespace std;

#define NODE typename LinkedList<T>::Node*

template <typename T>
class LinkedList {
public:
    void AddHead(const T& data); //Adds new node to the beginning of the list
    void AddTail(const T& data); //Adds new node to the end of the list
    LinkedList(); //Default constructor
    LinkedList(const LinkedList<T>& list); //Copy constructor

    struct Node {
        /*Individual node that stores the data*/
        T data;
        Node* prev;
        Node* next;
        Node(); //Default constructor for node
        Node(T _data); //Data constructor for node
        Node(T _data, Node* _prev, Node* _next); //Full constructor for node
    };
private:
    NODE head = nullptr;
    NODE tail = nullptr;
    unsigned int count;

};

/*Function definitions*/

template <typename T>
void LinkedList<T>::AddHead(const T& data) {
    NODE tempRef = new Node(data, nullptr, head);
    head->prev = tempRef;
    head = tempRef;
    delete tempRef;
    count++;
}

template <typename T>
void LinkedList<T>::AddTail(const T& data) {
    NODE tempRef = new Node(data, tail, nullptr);
    tail->next = tempRef;
    tail = tempRef;
    delete tempRef;
    count++;
}

template <typename T>
LinkedList<T>::LinkedList() {
    count = 0;
    head = nullptr;
    tail = nullptr;
}

template <typename T>
LinkedList<T>::LinkedList(const LinkedList<T>& list) {
    this->head = list.head;
    this->tail = list.tail;
    this->count = list.count;
}

/*Node Constructors*/

template <typename T>
LinkedList<T>::Node::Node() {
    next = nullptr;
    prev = nullptr;
}

template <typename T>
LinkedList<T>::Node::Node(T _data) {
    next = nullptr;
    prev = nullptr;
    data = _data;
}

template <typename T>
LinkedList<T>::Node::Node(T _data, Node* _prev, Node* _next) {
    next = _next;
    prev = _prev;
    data = _data;
}

Upvotes: 1

Views: 999

Answers (2)

Vlad from Moscow
Vlad from Moscow

Reputation: 311048

The both functions AddHead and AddTail have a serious bug because the allocated node is at once deleted

head = tempRef;
delete tempRef;

and

tail = tempRef;
delete tempRef;

So the pointers head and tail have invalid values.

Moreover the functions do not update tail and head correspondingly in each function.

And initially the both pointers are equal to nullptr. So these statements

head->prev = tempRef;

and

tail->next = tempRef;

result in undefined behavior.

The function AddHead can be defined the following way

template <typename T>
void LinkedList<T>::AddHead(const T& data) {
    NODE tempRef = new Node(data, nullptr, head);

    if ( head == nullptr )
    {
        head = tail = tempRef;
    }
    else
    {
        head = head->prev = tempRef;
    }

    count++;
}

And the function AddTail can look like

template <typename T>
void LinkedList<T>::AddTail(const T& data) {
    NODE tempRef = new Node(data, tail, nullptr);

    if ( tail == nullptr )
    {
        tail = head = tempRef;
    }
    else
    {
        tail = tail->next = tempRef;
    }

    count++;
}

The copy constructor (and the copy assignment operator) either should be defined as deleted or shall make a deep copy of the list passed as the argument.

Otherwise two lists will try to delete the same nodes two times (in the forgotten by you destructor).

The structure Node should be declared as a private class member.

Upvotes: 1

David Schwartz
David Schwartz

Reputation: 182819

You delete the nodes you add to the list in both AddTail and AddHead. This leaves pointers to garbage in the list.

Also, it's not clear how to use your linked list. You cannot call AddHead if head is nullptr (because AddHead dereferences head) and you cannot call AddTail if tail is nullptr. Since your constructor sets both head and tail equal to nullptr, what can you do next?

If it's legal for head to be nullptr, why does AddHead do head->prev = tempRef; without checking if head is nullptr?

I would strongly urge you to document your code. For example, what are the required preconditions for AddHead to be called? Is it supposed to be safe to call if head is nullptr or is it a requirement that it not be? Why is that not documented?

Upvotes: 0

Related Questions