Generic Doubly-Linked List (C++)

Bench 0 Tallied Votes 3K Views Share

This code snippet outlines a simple, no-frills linked list. Tested under MSVC++ 2003 and Comeau, but not guaranteed bug free. Snippet includes example main() .

This snippet is intended as an example of a possible implementation of a linked list class (Of which there are many variations) For a better linked list, use the STL <list> library.

#include <iostream>

template <typename T>
class double_linked
{
    struct node
    {
        T data;
        node* prev;
        node* next;
        node(T t, node* p, node* n) : data(t), prev(p), next(n) {}
    };
    node* head;
    node* tail;
public:
    double_linked() : head( NULL ), tail ( NULL ) {}
    template<int N>
    double_linked( T (&arr) [N]) : head( NULL ), tail ( NULL )
    {
        for( int i(0); i != N; ++i)
            push_back(arr[i]);
    }

    bool empty() const { return ( !head || !tail ); }
    operator bool() const { return !empty(); } 
    void push_back(T);
    void push_front(T);
    T pop_back();
    T pop_front();

    ~double_linked()
    {
        while(head)
        {
            node* temp(head);
            head=head->next;
            delete temp;
        }
    }
};

template <typename T>
void double_linked<T>::push_back(T data)
{
    tail = new node(data, tail, NULL);
    if( tail->prev )
        tail->prev->next = tail;

    if( empty() )
        head = tail;
}

template <typename T>
void double_linked<T>::push_front(T data)
{
    head = new node(data, NULL, head);
    if( head->next )
        head->next->prev = head;

    if( empty() )
        tail = head;
}

template<typename T>
T double_linked<T>::pop_back()
{
    if( empty() )
        throw("double_linked : list empty");
    node* temp(tail);
    T data( tail->data );
    tail = tail->prev ;

    if( tail )
        tail->next = NULL;
    else
        head = NULL ;

    delete temp;
    return data;
}

template<typename T>
T double_linked<T>::pop_front()
{
    if( empty() )
        throw("double_linked : list empty");
    node* temp(head);
    T data( head->data );
    head = head->next ;

    if( head )
        head->prev = NULL;
    else
        tail = NULL;

    delete temp;
    return data;
}


int main()
{
    int arr[] = { 4, 6, 8, 32, 19 } ;
    double_linked<int> dlist ( arr );
    dlist.push_back( 11 );
    dlist.push_front( 100 );
    while( dlist )
        std::cout << dlist.pop_back()  << " ";
}
rgpii 0 Newbie Poster

What is line 18 doing? It seems to me that line 16 is the constructor so I was confused as to what 18's purpose was. An explanation of line 11 would be great as well. Thanks.

mrnutty 761 Senior Poster

Thats called Initializer list

Bench 212 Posting Pro

the : after a constructor signature denotes the start of an initialisation list. Have a look here for a more detailed explanation:
http://www.cprogramming.com/tutorial/initialization-lists-c++.html


Line 18 is a template for an overloaded constructor which takes an array by-reference (Not by-pointer); Its not an essential part of the class though.

template<int N>
double_linked( T (&arr) [N]) : head( NULL ), tail ( NULL )

I added that to the example as a way to quickly initialise double_linked using an array of size N (where N is the template parameter, automatically deduced by the compiler).

An instance of that constructor is used here:

int arr[] = { 4, 6, 8, 32, 19 } ;
double_linked<int> dlist ( arr );

this call will create a constructor with the signature double_linked<int>::double_linked<5>(int (&)[5]) by way of deduction - the compiler knows that the array is size 5, and fills in the blank 'N'

rgpii 0 Newbie Poster

Ok, I have read about initialization lists. I have another question about line 11. Line eleven is the node constructor. It initializes data with the value t of type "T". I dont understand why "prev" and "next" are being initialized with pointers though. Isn't that saying that:

T data= T t
node* next=node* n//I don't understand the significance of setting
node* prev=node* p// next and prev to n and p.

I don't understand the significance of setting next and prev to n and p.
Thanks.

rgpii 0 Newbie Poster

Good call! haha can't believe i missed that.

Node* tempa=new Node(v,0,0);

It compiled and ran. Thanks for your help everyone!

xaviermars 0 Newbie Poster

Circular Double linked list
Description Create a circular doubly linked list. You are allowed the flexibility to determine the pieces of data to be stored in each node.

The method for adding the nodes to the list should ensure the list is always sorted. (the nodes should always be inserted in the right place)

i need help

idcristi 0 Newbie Poster

Very elegant. I learned some things. Thanks.
Question: wouldn't some processes like swapping elements be sped up if we replace the
T data with T* data ?

raptr_dflo 48 Posting Pro

The regulars here may well correct me (which would be awesome, btw), but first to answer your question: the point of linked lists is to make swapping elements efficient -- in particular, to swap any two nodes, you'd just swap the next and prev pointers of the nodes and their neighbors, rather than swapping the contents and leaving the nodes in place. You can draw it on paper as a set of boxes with content-values and arrows pointing from each to its previous and next boxes, and swap nodes (or insert, or delete, or whatever else) by erasing old arrows and drawing new ones so that following the arrows results in the correct new order.

Really not related, other than the question about whether to use pointers, because of the need to know a consistent size to allocate and compute index offsets, a polymorphic STL vector<> of objects needs to store pointers rather than instances. A specific example is wanting to store a list of Shape instances, where a specific shape would be an instance of subclass Triangle, Circle, or ZanyShape. You can't specify std::vector<Shape> because the compiler won't know how to grow/index the vector for different kinds of shapes, so instead (since a pointer is always the same size):

std::vector<Shape*> shape_vec;
Circle *c = new Circle(args);
shape_vec.push_back(c);
...

Meanwhile, happy linking!

Narue 5,707 Bad Cop Team Colleague

the point of linked lists is to make swapping elements efficient

Any linked data structure has that benefit, but it's not the point of linked lists[1]. I'd argue that the point of a linked list is the principle benefit, which would be efficient growth (ie. insertion and deletion) in the absence of random access.

>std::vector<Shape*> shape_vec;
This is the answer to idcristi's question. Since the list is generic, nothing stops you from storing a pointer type (it doesn't have to be polymorphic). Just like using pointers to speed up the passing of parameters, the same solution can be used to speed up the management of list data items.

Replacing T data with T *data actually makes the list less generic, and introduces some tricky pointer management problems.


[1] In fact, beyond the fundamental insertions and deletions, link surgery isn't as common in linked lists as you might think. Linked lists are generally reserved for simpler tasks where complex structure changes are unnecessary.

raptr_dflo 48 Posting Pro

In fact, beyond the fundamental insertions and deletions, link surgery isn't as common in linked lists as you might think. Linked lists are generally reserved for simpler tasks where complex structure changes are unnecessary.

Good point. While a fairly common recurring "programming test" given during interviews is "write code to reverse a singly-linked list", link surgery (as you so aptly put it) tends to show up more in maintaining a heap or a sorted-and-balanced tree of heavy-weight objects. But it's easier (for me, anyway) to start thinking in just the one-dimensional linear world of a list before getting more involved. Thanks for the additional insights!

mrnutty 761 Senior Poster

>>Any linked data structure has that benefit, but it's not the point of linked lists[1]. I'd argue that the point of a linked list is the principle benefit, which would be efficient growth (ie. insertion and deletion) in the absence of random access

I would like to point out one thing, in theory insertion/deletion is constant in a usual linked list implementation, but however one should think about it practically. Since the memory is all over the place in linked list, its not cache friendly, thus causes( or can cause ) a lot more cache misses, which would increase the latency time. Thus when you think you need linked list, you might be able to get away with using an array, especially if the order doesn't matter. If the order doesn't matter then you can achieve constant insertion and deletion with arrays too!! And its cache friendly. But as usual, it all depends. Its just a thought I figure to share.

luciolon 0 Newbie Poster

Hi,

First of all thank you for this code. I'm new in C++ programming and when I tries to use it by adding a single int I obtain the following error :

"DoubleLinked<int>::push_back(int)", referenced from:
_main in main.o
ld: symbol(s) not found
collect2: ld returned 1 exit status

Here is what I typed in my main function :

DoubleLinked<int> dlist; dlist.push_back(1);

Thanks for your help

Narue 5,707 Bad Cop Team Colleague

Please start a new thread in the forum and post your code.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.