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() << " ";
}
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.
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'
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.
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!
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
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 ?
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!
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.
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!
>>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.
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 statusHere is what I typed in my main function :
DoubleLinked<int> dlist; dlist.push_back(1);Thanks for your help
Please start a new thread in the forum and post your code.
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.