Home > Mobile >  linkedlist cannot be given data from std::string
linkedlist cannot be given data from std::string

Time:02-16

I made a simple linked list using a template, so the data can be more flexible

LinkedList.h

template<class T>
class Node{
public:
    Node<T> *next{nullptr};
    T value;
    Node(T value) : value{value}{}
};

template<class T>
class LinkedList{
private:
    int m_count;
public:
    Node<T> *head{nullptr};
    Node<T> *tail{nullptr};
    LinkedList();
public:
    void insertHead(T);
    void insertTail(T);
    int count();
    void info();

    //I didn't include all of the rest of the code

};

LinkedList.cc

template<class T>
LinkedList<T>::LinkedList(){}

template<class T>
void LinkedList<T>::insertHead(T val){
    
    Node<T> *node = new Node<T>{val};

    node->next = head;

    head = node;


    if(m_count == 0)
        tail = head;

      m_count;
}
template<class T>
void LinkedList<T>::insertTail(T val){
    
    if(m_count == 0){
        insertHead(val);
        return;
    }

    Node<T> *node = new Node<T>{val};

    tail->next = node;

    tail = node;

      m_count;
}
template<class T>
int LinkedList<T>::count(){
    return m_count;
}
template<class T>
void LinkedList<T>::info(){
   Node<T> *yosh = head;
    while(yosh != nullptr){
        std::cout<<yosh->value<<"->";
        yosh = yosh->next;
    }
    printf("nullptr");
}

by using the following data types it worked. / means or

LinkedList<int/char/double> ll;
ll.insertHead(1);
ll.insertHead(2);
ll.insertTail(3);
ll.info();//[2]->[1]->[3]->nullptr

but when using std::string

LinkedList<std::string> ll;
ll.insertHead("aziz");
ll.insertHead("tomo");
ll.insertHead("mario");
ll.info();//mario->tomo->aziz->nullptr

successful, but when I add another method, the result is

LinkedList<std::string> ll;
ll.insertHead("aziz");
ll.insertHead("tomo");
ll.insertHead("mario");
ll.insertTail("naruto");
ll.info();//Segmentation fault (core dumped)

what happens here, when I replace std::string with const char* everything is fine

LinkedList<const char*>ll;
ll.insertHead("tenmaru");
ll.insertHead("konohamaru");
ll.insertTail("ranmaru");
ll.info();//ok, no error

CodePudding user response:

It seems the problem is that not all data members of the class LinkedList are initialized inside the class definition

template<class T>
class LinkedList{
private:
    int m_count;
public:
    Node<T> *head{nullptr};
    Node<T> *tail{nullptr};
    LinkedList();
public:
    void insertHead(T);
    void insertTail(T);
    int count();

    //I didn't include all of the rest of the code

};

or inside the constructor

template<class T>
LinkedList<T>::LinkedList(){}

So the data member int m_count; stays uninitialized.

As a result the both functions insertHead and insertTail can invoke undefined behavior due to their if statements

if(m_count == 0)
    tail = head;

and

if(m_count == 0){
    insertHead(val);
    return;
}

You need to initialize the data member m_count for created objects of the type LinkedList.

CodePudding user response:

The question has been answered already by Vlad from Moscow. He is a true beginner with a rep of 254k :-) and has always good answers.

Additionally to your already very good code, I would like to show you 2 additional implementations to maybe give you some additionaly ideas.

Especially helpful is the sentinel approacht in the double linked list.

Please see:

Singly Linked List:

#include <iostream>
#include <iterator>
#include <initializer_list>
#include <algorithm>

// Very simple implementation of a forward list
template <class T>
class SinglyLinkedList {

    // The node
    struct Node {
        T data{};     // Data. Would normally be a templated argument
        Node* next{};   // And the pointer to the next node

        Node(const T& i, Node* n = nullptr) : data(i), next(n) {}; // Simple constructor to set a value and next pointer
    };

    Node* head{};       // This is the start of the list
    // It would be advisable to have a tail pointer. We use the more inefficient approach here
    Node* getLast() const { Node* n{ head }; while (n and n->next) n = n->next; return n; }

public:
    // Constructor / Destructor --------------------------------------------------------------------------------------------------------
    ~SinglyLinkedList() { clear(); }

    // Default constuctor
    SinglyLinkedList() {}   // Default

    // From an initialization list
    SinglyLinkedList(const std::initializer_list<T>& il) { clear();  for (const T& i : il) push_back(i); } // From initializer list

    // Copy constructor
    SinglyLinkedList(const SinglyLinkedList& other) { clear(); for (const T& i : other) push_back(i); }

    // Move constructor. Will steal the elements from the other 
    SinglyLinkedList(SinglyLinkedList&& other) noexcept { head = other.head; other.head = nullptr; }

    // Assignment operator
    SinglyLinkedList& operator = (const SinglyLinkedList& other) { clear(); for (const T& i : other) push_back(i); }

    // Move assignment operator 
    SinglyLinkedList& operator = (SinglyLinkedList&& other) { head = other.head; other.head = nullptr; }

    // Housekeeping --------------------------------------------------------------------------------------------------------------
    void clear() { Node* tmp{ head }; while (tmp) { Node* toDelete{ tmp }; tmp = tmp->next; delete toDelete; } head = nullptr; }
    int empty() const { return head == nullptr; }
    int size() const { int k{}; Node* n{ head }; while (n) {   k; n = n->next; } return k; }

    // Modify content --------------------------------------------------------------------------------------------------------------
    void push_front(const T& i) { Node* n = new Node(i); n->next = head; head = n; };
    void push_back(const T& i) { Node* n = new Node(i); Node* l = getLast(); if (l) l->next = n; else head = n; }
    void pop_front() { if (head) { Node* tmp = head->next; delete head; head = tmp; } }
    void pop_back() { // This is a little bit more difficult in a singly linked list
        if (head) {
            Node* n{ head }, * previous{};
            while (n and n->next) {
                previous = n;
                n = n->next;
            }
            delete n;
            if (previous)
                previous->next = nullptr;
            else
                head->next = nullptr;
        }
    }

    // Access elements --------------------------------------------------------------------------------
    T& front() const { return head ? head->data : 0; };
    T back() const { Node* n = getLast(); return n ? n->data : 0; }

    // Add iterator properties to class ---------------------------------------------------------------
    struct iterator {                           // Local class for iterator
        Node* iter{};                           // Iterator is basically a pointer to the node
        Node* head{};

        // Define alias names necessary for the iterator functionality
        using iterator_category = std::bidirectional_iterator_tag;
        using difference_type = std::ptrdiff_t;
        using value_type = T;
        using pointer = T*;
        using reference = T&;

        // Constructor
        iterator() {}
        iterator(Node* n, Node* h) : iter(n), head(h) {}

        // Dereferencing
        reference operator *() const { return iter->data; }
        pointer operator ->() const { return &iter->data; }

        // Aithmetic operations
        iterator& operator   () { if (iter) iter = iter->next; return *this; }
        iterator operator   (int) { iterator temp{ *this };   * this; return temp; }

        // Clumsy subtratcion
        iterator& operator --() { Node* tmp = head; while (tmp and tmp->next != this->iter) tmp = tmp->next; iter = tmp;  return *this; }
        iterator operator --(int) { iterator temp{ *this }; --* this; return temp; }

        iterator operator  (const difference_type& n) const {
            iterator temp{ *this };  difference_type k{ n }; if (k > 0) while (k--)  temp; else while (k  )--temp; return temp;
        }
        iterator operator  =(const difference_type& n) {
            difference_type k{ n }; if (k > 0) while (k--)  * this; else while (k  )--* this; return *this;
        };
        iterator operator -(const difference_type& n) const {
            iterator temp{ *this };  difference_type k{ n }; if (k > 0) while (k--)--temp; else while (k  )  temp; return temp;
        }
        iterator operator -=(const difference_type& n) {
            difference_type k{ n }; if (k > 0) while (k--)--* this; else while (k  )  * this; return *this;
        };

        // Comparison
        bool operator != (const iterator& other) const { return iter != other.iter; }
        bool operator == (const iterator& other) const { return iter == other.iter; }
        bool operator < (const iterator& other) const { return iter < other.iter; }
        bool operator > (const iterator& other) const { return iter > other.iter; }
        bool operator <= (const iterator& other) const { return iter <= other.iter; }
        bool operator >= (const iterator& other) const { return iter >= other.iter; }

        // Difference. Also complicated, because no random access
        difference_type operator-(const iterator& other) const {
            difference_type result{};
            Node* n{ iter };
            while (n and n != other.iter) {
                  result;
                n = n->next;
            }
            return result;
        }
    };

    // Begin and end function to initialize an iterator
    iterator begin() const { return iterator(head, head); }
    iterator end() const { return iterator(nullptr, head); }

    // Functions typcical for forward lists ----------------------------------------------------------------------
    // Easy, becuase we can operate form the current iterator and do not need the "previous" element
    iterator insertAfter(iterator& pos, const T& i) {
        iterator result(nullptr, head);
        if (pos.iter and pos.iter->next) {
            Node* n = new Node(i, pos.iter->next);
            pos.iter->next = n;
            result.iter = n;
        }
        return result;
    }
    iterator eraseAfter(iterator& pos) {
        iterator result(nullptr, head);
        if (pos.iter and pos.iter->next) {
            Node* tmp = pos.iter->next->next;
            delete pos.iter->next;
            pos.iter->next = tmp;
            result.iter = pos.iter->next;
        }
        return result;
    }
};
// Test/Driver Code
int main() {

    // Example for initilizer list
    SinglyLinkedList<int> sllbase{ 5,6,7,8,9,10,11,12,13,14,15 };
    // Show move constructor
    SinglyLinkedList<int> sll(std::move(sllbase));

    // Add some values in the front
    sll.push_front(4);
    sll.push_front(3);
    sll.push_front(2);
    sll.push_front(1);

    // Delete 1st element (Number 1)
    sll.pop_front();
    // Delete last element
    sll.pop_back();

    // Use a std::algorithm on our custom linked list. Works because we have an interator
    SinglyLinkedList<int>::iterator iter = std::find(sll.begin(), sll.end(), 8);
      iter;
    --iter;

    // Now add an element after 8
    iter = sll.insertAfter(iter, 88);
    // And delete the 9
    iter = sll.eraseAfter(iter);

    // Use range based for loop. Works because, we have iterators
    for (int i : sll)
        std::cout << i << ' ';


    // Reverse Output
    std::cout << "\n\n";
    std::reverse_iterator<SinglyLinkedList<int>::iterator> riter = std::make_reverse_iterator(sll.end());
    std::reverse_iterator<SinglyLinkedList<int>::iterator> riterEnd = std::make_reverse_iterator(sll.begin());

    for (; riter != riterEnd;   riter)
        std::cout << *riter << ' ';
    std::cout << "\n\n";

    return 0;
}

Double linked list. Similar to std::list

#include <iostream>
#include <iterator>
#include <vector>
#include <type_traits>
#include <initializer_list>
#include <algorithm>
#include <list>

// ------------------------------------------------------------------------------------------------
// This would be in a header file -----------------------------------------------------------------

// Type trait helper to identify iterators --------------------------------------------------------
template<typename T, typename = void>
struct is_iterator { static constexpr bool value = false; };
template<typename T>
struct is_iterator<T, typename std::enable_if<!std::is_same<typename std::iterator_traits<T>::value_type, void>::value>::type> {
    static constexpr bool value = true;
};

// The List class ---------------------------------------------------------------------------------
template <typename T>
class List {
    // Sub class for a Node -----------
    struct Node {
        Node* next{};
        Node* previous{};
        T data{};
        Node(Node* const n, Node* const p, const T& d) : next(n), previous(p), data(d) {}
        Node(Node* const n, Node* const p) : next(n), previous(p) {}
        Node() {}
    };

    // Private list data and functions --------
    size_t numberOfElements{};
    Node* head{};
    void init() { head = new Node(); head->next = head; head->previous = head; numberOfElements = 0; }

public:
    struct iterator;    // Forward declaration

    // Constructor --------------------
    List() { init(); }
    explicit List(const size_t count, const T& value) { init(); insert(begin(), count, value); };
    explicit List(const size_t count) { init(); insert(begin(), count); }
    template <typename Iter>
    List(const Iter& first, const Iter& last) { init(); insert(begin(), first, last); }
    List(const List& other) { init(), insert(begin(), other.begin(), other.end()); };
    List(List&& other) : head(other.head), numberOfElements(other.numberOfElements) { other.init(); }
    List(const std::initializer_list<T>& il) { init(); insert(begin(), il.begin(), il.end()); }
    template <int N> List(const T(&other)[N]) { init(); insert(begin(), std::begin(other), std::end(other)); }
    template <int N> List(T(&other)[N]) { init(); insert(begin(), std::begin(other), std::end(other)); }


    // Assignment ---------------------
    List& operator =(const List& other) { clear(); insert(begin(), other.begin(), other.end()); return *this; }
    List& operator =(List&& other) { clear(); head = other.head; numberOfElements = other.numberOfElements; other.init(); return *this; }
    List& operator =(const std::initializer_list<T>& il) { clear(); insert(begin(), il.begin(), il.end()); return *this; }
    template <int N> List& operator =(const T(&other)[N]) { clear(); insert(begin(), std::begin(other), std::end(other)); return *this; }
    template <int N> List& operator =(T(&other)[N]) { clear(); insert(begin(), std::begin(other), std::end(other)); return *this; }

    void assign(const size_t count, const T& value) { clear(); insert(begin(), count, value); }
    void assign(const std::initializer_list<T>& il) { clear(); insert(begin(), il.begin(), il.end()); }
    template <typename Iter> void assign(const Iter& first, const Iter& last) { clear(); insert(begin(), first, last); }
    template <int N> void assign(const T(&other)[N]) { clear(); insert(begin(), std::begin(other), std::end(other)); return *this; }
    template <int N> void assign(T(&other)[N]) { clear(); insert(begin(), std::begin(other), std::end(other)); return *this; }

    // Destructor ---------------------
    ~List() { clear(); }

    // Element Access -----------------
    T& front() { return *begin(); }
    T& back() { return *(--end()); }

    // Iterators ----------------------
    iterator begin() const { return iterator(head->next, head); }
    iterator end() const { return iterator(head, head); }

    // Capacity -----------------------
    size_t size() const { return numberOfElements; }
    bool empty() { return size() == 0; }

    // Modifiers ----------------------
    void clear();

    iterator insert(const iterator& insertBeforePosition, const T& value);
    iterator insert(const iterator& insertBeforePosition);
    template <class Iter, std::enable_if_t<is_iterator<Iter>::value, bool> = true>
    iterator insert(const iterator& insertBeforePosition, const Iter& first, const Iter& last);
    iterator insert(const iterator& insertBeforePosition, const size_t& count, const T& value);
    iterator insert(const iterator& insertBeforePosition, const std::initializer_list<T>& il);

    iterator erase(const iterator& posToDelete);
    iterator erase(const iterator& first, const iterator& last);


    void push_back(const T& d) { insert(end(), d); }
    void pop_back() { erase(--end()); };

    void push_front(const T& d) { insert(begin(), d); }
    void pop_front() { erase(begin()); };

    void resize(size_t count);
    void resize(size_t count, const T& value);

    void swap(List& other) { std::swap(head, other.head); std::swap(numberOfElements, other.numberOfElements); }

    // Operations --------------------
    void reverse();

    // Non standard inefficient functions --------------------------
    T& operator[](const size_t index) const { return begin()[index]; }

    // ------------------------------------------------------------------------
    // Define iterator capability ---------------------------------------------
    struct iterator {

        // Definitions ----------------
        using iterator_category = std::bidirectional_iterator_tag;
        using difference_type = std::ptrdiff_t;
        using value_type = T;
        using pointer = T*;
        using reference = T&;

        // Data -----------------------
        Node* iter{};
        Node* head{};

        // Constructor ----------------
        iterator(Node* const node, Node* const h) : iter(node), head(h) {};
        iterator() {};

        // Dereferencing --------------
        reference operator*() const { return iter->data; }
        reference operator->() const { return &**this; }

        // Arithmetic operations ------
        iterator operator  () { iter = iter->next; return *this; }
        iterator operator  (int) { iterator tmp = *this;   * this; return tmp; }
        iterator operator--() { iter = iter->previous; return *this; }
        iterator operator--(int) { iterator tmp = *this; --* this; return tmp; }

        iterator operator  (const difference_type& n) const {
            iterator temp{ *this };  difference_type k{ n }; if (k > 0) while (k--)  temp; else while (k  )--temp; return temp;
        }
        iterator operator  =(const difference_type& n) {
            difference_type k{ n }; if (k > 0) while (k--)  * this; else while (k  )--* this; return *this;
        };
        iterator operator -(const difference_type& n) const {
            iterator temp{ *this };  difference_type k{ n }; if (k > 0) while (k--)--temp; else while (k  )  temp; return temp;
        }
        iterator operator -=(const difference_type& n) {
            difference_type k{ n }; if (k > 0) while (k--)--* this; else while (k  )  * this; return *this;
        };
        // Comparison ----------------- (typical space ship implementation)
        bool operator ==(const iterator& other) const { return iter == other.iter; };
        bool operator !=(const iterator& other) const { return iter != other.iter; };
        bool operator < (const iterator& other) const { return other.iter - iter < 0; };
        bool operator <= (const iterator& other) const { return other.iter - iter <= 0; };
        bool operator > (const iterator& other) const { return other.iter - iter > 0; };
        bool operator >= (const iterator& other) const { return other.iter - iter >= 0; };

        // Special non standard functions -----------------
        difference_type operator-(const iterator& other) const;
        reference operator[] (const size_t index);
    };
};


// ------------------------------------------------------------------------------------------------
// Implementation of list functions. This would normally go into a TCC file -----------------------

// List class functions ---------------
template <typename T>
void List<T>::clear() {

    for (Node* nextNode{}, * currentNode(head->next); currentNode != head; currentNode = nextNode) {
        nextNode = currentNode->next;
        delete currentNode;
    }
    init();
}
template <typename T>
typename List<T>::iterator List<T>::insert(const List<T>::iterator& insertBeforePosition, const T& value)
{
    Node* nodeInsertBeforePosition = insertBeforePosition.iter;
    Node* newNode = new Node(nodeInsertBeforePosition, nodeInsertBeforePosition->previous, value);
    nodeInsertBeforePosition->previous = newNode;
    (newNode->previous)->next = newNode;
      numberOfElements;
    return iterator(newNode, head);
}
template <typename T>
typename List<T>::iterator List<T>::insert(const List<T>::iterator& insertBeforePosition)
{
    Node* nodeInsertBeforePosition = insertBeforePosition.iter;
    Node* newNode = new Node(nodeInsertBeforePosition, nodeInsertBeforePosition->previous);
    nodeInsertBeforePosition->previous = newNode;
    (newNode->previous)->next = newNode;
      numberOfElements;
    return iterator(newNode, head);
}

template <typename T>
template <class Iter, std::enable_if_t<is_iterator<Iter>::value, bool>>
typename List<T>::iterator List<T>::insert(const List<T>::iterator& insertBeforePosition, const Iter& first, const Iter& last) {
    iterator result(insertBeforePosition.iter, head);
    if (first != last) {
        result = insert(insertBeforePosition, *first);
        Iter i(first);
        for (  i; i != last;   i)
            insert(insertBeforePosition, *i);
    }
    return result;
}

template <typename T>
typename List<T>::iterator List<T>::insert(const List<T>::iterator& insertBeforePosition, const size_t& count, const T& value) {

    iterator result(insertBeforePosition.iter, head);
    if (count != 0u) {
        result = insert(insertBeforePosition, value);
        for (size_t i{ 1u }; i < count;   i)
            insert(insertBeforePosition, value);
    }
    return result;
}

template <typename T>
typename List<T>::iterator List<T>::insert(const List<T>::iterator& insertBeforePosition, const std::initializer_list<T>& il) {
    return insert(insertBeforePosition, il.begin(), il.end());
}

template <typename T>
typename List<T>::iterator List<T>::erase(const List<T>::iterator& posToDelete) {

    iterator result = posToDelete;
      result;

    Node* nodeToDelete = posToDelete.iter;

    if (nodeToDelete != head) {

        nodeToDelete->previous->next = nodeToDelete->next;
        nodeToDelete->next->previous = nodeToDelete->previous;

        delete nodeToDelete;
        --numberOfElements;
    }
    return result;
}

template <typename T>
typename List<T>::iterator List<T>::erase(const List<T>::iterator& first, const List<T>::iterator& last) {
    iterator result{ end() };
    if (first == begin() && last == end())
        clear();
    else {
        while (first != last)
            first = erase(first);
        result = last;
    }
    return result;
}

template <typename T>
void List<T>::resize(size_t count) {
    if (numberOfElements < count)
        for (size_t i{ numberOfElements }; i < count;   i)
            insert(end());
    else
        while (count--)
            pop_back();
}
template <typename T>
void List<T>::resize(size_t count, const T& value) {
    if (numberOfElements < count)
        for (size_t i{ numberOfElements }; i < count;   i)
            insert(end(), value);
    else
        while (count--)
            pop_back();
}
template <typename T>
void List<T>::reverse() {
    const Node* oldHead = head;

    for (Node* nptr = head; ; nptr = nptr->previous) {
        std::swap(nptr->next, nptr->previous);
        if (nptr->previous == oldHead) // Previous was the original next
            break;
    }
}

// ------------------------------------
// Iterator functions -----------------
template <typename T>
typename List<T>::iterator::difference_type List<T>::iterator::operator-(const iterator& other) const {

    difference_type result{};
    Node* nptr = head;

    int indexThis{ -1 }, indexOther{ -1 }, index{};

    do {
        nptr = nptr->next;
        if (nptr == iter)
            indexThis = index;
        if (nptr == other.iter)
            indexOther = index;
          index;
    } while (nptr != head);

    if (indexThis >= 0 and indexOther >= 0)
        result = indexThis - indexOther;
    return result;
}
template <typename T>
typename List<T>::iterator::reference List<T>::iterator::operator[] (const size_t index) {
    Node* nptr = head->next;
    for (size_t i{}; i < index and nptr != head;   i, nptr = nptr->next)
        ;
    return nptr->data;
}

// ------------------------------------------------------------------------------------------------
// This would be in a cpp file --------------------------------------------------------------------
int main() {


    List<int> list3{ 10,20 };
    List<int>::iterator l3 = list3.end();
    for (int k = 0; k < 10;   k) {
        std::cout << *l3 << ' ';
        --l3;
    }
    std::cout << '\n';

    // Custom list
    List<int> list2{ 1, 2, 3, 4, 5 };

    for (int i : list2)
        std::cout << i << ' '; std::cout << '\n';

    // Delta works
    std::cout << list2.begin() - list2.end() << '\n';
    std::cout << list2.end() - list2.begin() << '\n';

    // Hopp Count works
    List<int>::iterator i = list2.end();
    while (i-- != list2.begin())
        std::cout << *i << ' '; std::cout << '\n';
}
  • Related