Generic Doubly-Linked List (C++)

0

By Bench on Jul 18th, 2007 10:42 pm

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()  << " ";
}

3 Years Ago

0

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.

rgpii

Newbie Poster

22 posts since Oct 2009

Reputation Points: 10

Solved Threads: 0

Skill Endorsements: 0

3 Years Ago

0

Thats called Initializer list

firstPerson

Industrious Poster

4,044 posts since Dec 2008

Reputation Points: 851

Solved Threads: 625

Skill Endorsements: 15

3 Years Ago

1

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'

Bench

Posting Pro

577 posts since Feb 2006

Reputation Points: 307

Solved Threads: 63

Skill Endorsements: 0

3 Years Ago

0

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

Newbie Poster

22 posts since Oct 2009

Reputation Points: 10

Solved Threads: 0

Skill Endorsements: 0

3 Years Ago

0

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!

rgpii

Newbie Poster

22 posts since Oct 2009

Reputation Points: 10

Solved Threads: 0

Skill Endorsements: 0

3 Years Ago

0

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

xaviermars

Newbie Poster

1 post since Apr 2010

Reputation Points: 10

Solved Threads: 0

Skill Endorsements: 0

1 Year Ago

0

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 ?

idcristi

Newbie Poster

1 post since Jun 2011

Reputation Points: 10

Solved Threads: 0

Skill Endorsements: 0

1 Year Ago

0

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!

raptr_dflo

Practically a Master Poster

605 posts since Aug 2010

Reputation Points: 76

Solved Threads: 83

Skill Endorsements: 1

1 Year Ago

0

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.

Narue

Bad Cop

Team Colleague

15,460 posts since Sep 2004

Reputation Points: 6,483

Solved Threads: 1,407

Skill Endorsements: 54

1 Year Ago

0

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!

raptr_dflo

Practically a Master Poster

605 posts since Aug 2010

Reputation Points: 76

Solved Threads: 83

Skill Endorsements: 1

1 Year Ago

1

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

firstPerson

Industrious Poster

4,044 posts since Dec 2008

Reputation Points: 851

Solved Threads: 625

Skill Endorsements: 15

1 Year Ago

0

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

luciolon

Newbie Poster

6 posts since Sep 2011

Reputation Points: 10

Solved Threads: 0

Skill Endorsements: 0

1 Year Ago

0

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

Narue

Bad Cop

Team Colleague

15,460 posts since Sep 2004

Reputation Points: 6,483

Solved Threads: 1,407

Skill Endorsements: 54