Quick question regarding doubly linked lists

[AltF4me]

I'm developing a doubly linked list. Now the way I'm currently navigating it is by using a current position pointer, that starts at the tail and then loops round however many times you need (you'll tell the function) and it will then get to that node.

Now, I'm having to do this many times.. when I want to look at a certain index, when I want to delete an item at a certain index, inserting, etc etc etc..

Is there a more efficient way of doing this? Or is this just how it's typically done?

Many Thanks! :)

[mrnutty]

Nope. That's the limitation of the linked list. You need to transverse the
list to get to a node. Whereas with arrays, you can access the data by
indexing. But using linked list, you can delete and insert element very fast,
O(1) to be exact.

[AltF4me]

Thanks very much. Just wanted to make sure there wasn't a better way!

[AltF4me]

Hiya,
Another question about linked lists! as this one is driving me crazy! Literally spent a good 4 hours on this and I don't understand why at all!

I've got it working so that I can insert a value after a certain index.. worked this out within 5 seconds. However, for inserting a value before doesn't seem to want to work at all! It should be practically the same code!.. here's what I'm using for the functions so far:

Works great...

void DLL::insertAfter(const int &insertData, const int index)
{
	_current = _tail;
	Node *newInsert = new Node;
	newInsert->setData(insertData);

	for (int i = 0; i < index; ++i)
	{
		_current = _current->_next; //Find the index
	}
	
	newInsert->_previous = _current;
	newInsert->_next = _current->_next;
	_current->_next = newInsert;

	++_listSize;
}

Doesn't seem to work at all

void DLL::insertBefore(const int &insertData, const int index)
{
	_current = _tail;
	Node *newInsert = new Node;
	newInsert->setData(insertData);

	for (int i = 0; i < index; ++i)
	{
		_current = _current->_next;
	}

	
	newInsert->_next = _current;
	newInsert->_previous = _current->_previous;
	_current->_previous = newInsert;
	
	
	++_listSize;
}

The second chunk of code just doesn't seem to change anything at all. Am I missing something really obvious here?

Many Thanks

[nezachem]

Both snippets suffer the same problem. They do not update the one pointer (current->next->previous and current->previous->next respectively). The first snippet gives an impression of working because of the way you traverse the list. Try to traverse it in both directions and you will see the problem.

[Lerner]

Use pencil and paper. I think you'll find you need to use 4 pointers, current, and a temorary node.

Insert after current:
temp = current->next; //keep track of this value

//attach newInsert after current
current->next = newInsert;
newInsert->previous = current;

//attach whatever current used to point to after newInsert
newInsert->next = temp;
temp->previous = newInsert;

Insert before current:
temp = current->previous; //keep track of this value

//insert new value before current
newInsert->next = current;
current->previous = newInsert;

//attach what used to point to current to newInsert.
temp->next = newInsert;
newInsert->previous = temp;

At least I think that will work. Been a while since I've written a doubly linked list since the STL list class is doubly linked and written already.

[AltF4me]

Couldn't get it to work with that code :( (kept getting run-time errors) but now that I've had some sleep I decided to have another look on google and found some pseduocode on wikipedia that seemed to work :)
http://en.wikipedia.org/wiki/Doubly-linked_list

function insertAfter(Node node, Node newNode)
     newNode.next := node.next
     newNode.prev := node
     node.next.prev := newNode
     node.next      := newNode

Then for insertingBefore just call the above function but with an index of 2 lower (as 1 lower would be pointing to that current element..)

Cheers again!

[n.utiu]

The most efficient way would be to use std::list . :D

[AltF4me]

The most efficient way would be to use std::list . :D

Maybe so but I have to develop it myself for my uni coursework, so I need to learn it properly :)