Freeing a linked list

Iv'e had a look at a few tutorials on linked lists because iv'e never really used them before i've always used dynamic arrays insted, and one thing is puzzling me is that none of them really say anything about freeing a linked list the same way you would free a dynamic array.
Do they need to be freed at all?
say for example i have 3 nodes and i want to delete the middle node, do i just change the pointer in node 1 to point to node 3 and thats it? or would i have to free node 2 and then change the pointer in node 1??

make a temporary for holding the middle node then point the node 1 to node 3 then free the one that holds the middle node.

Correct me if I'm wrong but that's what I did when I was using linked list a few years ago.

Thanks
Sarah22

this is the basic structure of a doubly linked list, which is most common.
I am writing all this right now, so there might be errors, but you should get the jist of it.

Code:

---

template<class T>class list{
public:
      struct node{   
          node* prev, next;
          T objectbeingheld;
      };
      node*curr;
    list(): curr(NULL) {}
      insert(T& object){// inserts before *this
            if(curr==NULL){// this is the head node
                    objectbeinghelp = object;// you can use pointers of what ever you want
            } // otherwise there is something in front of *this
              node* temp = new node;
              temp->prev = this->curr->prev;
              temp->next = this;
              temp->objectbeingheld=object;
                prev = temp;
      }// end of insert
      remove(){// remove this node!!!
              if(prev == NULL){// we are the head node.. ohh crap!
                    if(next==NULL){// we are empty what the hell !!
                            return;
                    }// there is a node behind us.. yay, we are loved!
                      next->prev = NULL;// make sure the next node KNOWS it is the head..
                     
};

---

sorry I started getting tired and decided that I didn't want to write the code. Maybe you can decipher it, eh? I forgot that I needed to create a container to hold the nodes...

the term node is what is typically called each object held in a linked list. So, create a container to hold those nodes. Allocate new ones on an insert call, and call delete on a removal. I am going to sleep now

Elaboration on above post:

Code:

---

#include <iostream>

// Boring class to test list with
class rect {
public:
        rect() { m_width = 0; m_height = 0; }
        rect(unsigned int width, unsigned int height) { m_width = width; m_height = height; }
       
        unsigned int getwidth() const { return m_width; }
        unsigned int getheight() const { return m_height; }
       
        void setwidth(unsigned int width) { m_width = width; }
        void setheight(unsigned int height) { m_height = height; }
private:
        unsigned int m_width;
        unsigned int m_height;
};
       

template <class T>
class list {
public:
        list();
        // Same as calling empty: deletes nodes and sets pointers to NULL
        ~list();
       
        // Overloaded [] operator: same as calling at(index)
        T* operator[](size_t index);
        void add(T obj);
        // Should throw exceptions on out-of-bounds?
        T* at(size_t index);
        size_t size() const;
        void remove(size_t index);
        // Clear list
        void empty();
private:
        struct node {
                node* next;
                node* prev;
                T obj;
        };
        struct node *m_head;
        struct node *m_tail;
        size_t m_size;
};

template <class T>
list<T>::list() {
        m_head = NULL;
        m_tail = NULL;
        m_size = 0;
}

template <class T>
list<T>::~list() {
        empty();
}

template <class T>
void list<T>::empty() {
        if (m_size) {
                for (size_t i = 0; i < m_size; i++)
                        remove(i);
        }
        m_head = NULL;
        m_tail = NULL;
}

template<class T>
size_t list<T>::size() const {
        return m_size;
}

template<class T>
void list<T>::remove(size_t index) {
        if (!m_head || index < 0 || index >= m_size)
                return;
       
        struct node* cur = m_head;
        for (size_t i = 0; i < index; i++)
                cur = cur->next;
       
        if (cur == m_head) {
                // Delete beginning of list
                m_head = cur->next;
                if (m_head)
                        m_head->prev = NULL;
        } else if (cur == m_tail) {
                // Delete end of list
                m_tail = cur->prev;
                m_tail->next = NULL;
        } else {
                // Inbetween nodes
                cur->prev->next = cur->next;
                cur->next->prev = cur->prev;
        }
       
        delete cur;
        m_size--;
}

template<class T>
T* list<T>::operator[](size_t index) {
        return at(index);
}

template <class T>
T* list<T>::at(size_t index) {
        // Todo: Exceptions?
        if (index < 0 || index >= m_size || m_size == 0)
                return NULL;
       
        struct node* cur = m_head;
       
        // Move through list
        for (size_t i = 0; i < index; i++)
                cur = cur->next;
       
        return &cur->obj;
}

template <class T>
void list<T>::add(T obj) {
        struct node* newnode = new struct node;
       
        if (m_head) {
                // First node in list
                newnode->next = NULL;
                newnode->prev = m_tail;
                newnode->obj = obj;
                m_tail->next = newnode;
                m_tail = newnode;
        } else {
                // Append to end
                newnode->next = NULL;
                newnode->prev = NULL;
                newnode->obj = obj;
                m_head = newnode;
                m_tail = m_head;
        }
        m_size++;
}       
               
int main(int argc, char* argv[]) {
        list<rect> rects;
               
        rects.add(rect(5, 5));
        rects.add(rect(3, 7));
        rects.add(rect(2, 4));
        rects.add(rect(10, 10));
       
        rects.remove(1);
       
        rects[0]->setwidth(4);
       
        for (size_t i = 0; i < rects.size(); i++)
                std::cout << rects[i]->getwidth() << "x" << rects[i]->getheight() << std::endl;
       
        return 0;
}

---

cheers for the info guys