Linked List

[shane54747]

Can i have some tips on this question please.

write a function that deletes the ith node from a circular linked list.

Any help would be welcome.

[maikel]

In detail, it depends on your current implementation of a list. There is very easy way to do so with modulo. [slowly i get the feeling im only telling ya guys about modulo in this forum.. ;-)]

if there is a request like

     erase(position);

then just calc 'n = position % elems_number'. And process n times through an iterator to your wished element.

Here is one possibility of doing so. You can guess the rest of this implementation of a list.
SYNTAX: m_variable are member vars of currect object. My List class is friend of Node class

	template <typename T>
	void List<T>::erase(unsigned int pos)
	{
		Node<T> *node = m_begin;

		if (m_size <= 0) // size of list. cant be < 0, but 0 means empty
			return;      // but if list is empty, there is nothing to erase

                // now go to the wished position. you could now even decide now which direction to go 
                // halfed size of your list and go the shorter way (forward or backward, if possible)
		pos %= m_size;
		while (pos > 0) {
			node = node->next(); // proceed to your n-th position
			pos--;
		}
		
                // here you do your exchange
		Node<T> *next = node->next(), *prev = node->prev();
		next->m_prev = prev;
		prev->m_next = next;

                // its pretty important to delete node now, and not after next and prev are set.
                // because next and prev could be same, they even could be node itself.
                // thats the case if you have only one element in list. then its something like this
                // node->next = node = node->prev
		delete node;
		if (--m_size == 0)
			m_begin = NULL;
	}

If you have questions related to the code, feel free to ask. Sometimes it is really hard to understand snapshots like this of a complete code.


Maikel