Freeing a linked list

This is a discussion on Freeing a linked list within the C++ Programming forums, part of the General Programming Boards category; Iv'e had a look at a few tutorials on linked lists because iv'e never really used them before i've always ...

  1. #1
    Master n00b Matty_Alan's Avatar
    Join Date
    Jun 2007
    Location
    Bloody Australia Mate!
    Posts
    96

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

  2. #2
    Registered User
    Join Date
    May 2009
    Posts
    64
    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

  3. #3
    Registered User
    Join Date
    Mar 2010
    Posts
    68

    data structure question.. oohh how cool

    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

  4. #4
    Registered User
    Join Date
    Feb 2010
    Posts
    38
    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;
    }
    Last edited by nicoqwertyu; 04-17-2010 at 10:03 PM.

  5. #5
    Master n00b Matty_Alan's Avatar
    Join Date
    Jun 2007
    Location
    Bloody Australia Mate!
    Posts
    96
    cheers for the info guys

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 10:03 AM
  2. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 05:46 PM
  3. Linked List
    By jpipitone in forum C Programming
    Replies: 4
    Last Post: 03-30-2003, 08:27 PM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 08:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21