how to create an empty doubly linked list?

if i have the following node class

class Node {
 public:
Node() { next = NULL; prev = NULL; }
~Node() {}
 public :
Node *next;
Node *prev;
T data;
 };

how do i create an empty lin开发者_如何学Cked list in the function

LinkedList::LinkedList()

my linked list classs has the following functions

 void append(T item);
T get(int idx);
void insert(int idx, T item);
void map(T (*pf)(T item));
T remove(int index);
int size();
void unshift(T item);

---

Doubly linked lists usually have a reference to the first and (sometimes) last element in the list.

Node *first, *last;

In your constructor, just set these to NULL. Then make an isEmpty method which checks for this condition, and you're done.

LinkedList::LinkedList()
{
    first = NULL;
    last = NULL;
}

bool LinkedList::isEmpty()
{
    return (first == NULL) && (last == NULL);
}

---

My solution (from pre-standard days) has always been to have a NodeBase class with the pointers, and derive from that to add the data. This allows my DLList object to contain a NodeBase, rather than it having to manage the pointers seperately. And NodeBase always had a constructor which linked it to nowhere—typically, by setting both pointers to this, e.g.:

struct NodeBase
{
    NodeBase* next;
    NodeBase* prec;
    NodeBase()
        : next(this)
        , prec(this)
    {
    }
    ~NodeBase()
    {
        next->prec = prec;
        prec->next = next;
    }
};

Doing so means that there's no clear end of list indicator (the actual list is circular), so you have to keep track of where you started when iterating, but it makes so many other operations so much easier.

---

As the other answers indicate, there's more than one way to do it. Here's an especially peculiar one for your information: although it's not portable C so perhaps is better suited to assembly:

struct Node {
    Node *next;
    Node *prev;
};

struct List {
    Node *a;
    Node *b;
    Node *c;
    List : a(tail()), b(0), c(head())
    Node *head() { return (Node *)&a; }
    Node *tail() { return (Node *)&b; }
};

So, a struct contains a dummy head node (whose prev pointer of course is always 0) and a dummy tail node (whose next pointer is always 0), and to save a massive sizeof(Node*) bytes storage per list, they overlap (which is what makes it non-portable). The overlap isn't essential, you could put two Node in the List instead of three Node*.

This is a useful structure in that it gives you both a "before-the-beginning" and an "after-the-end" node in the list, which means you can perform all of remove, insert_after and insert_before on nodes without reference to the list head at all. In that respect it's like James's circular list, but unlike his you can also check for the ends by looking for the null pointer - also without reference to the head.

File under, "tricks I don't need to play".