Double Linked List, move?

[alex067]

I'm just curious if it's possible to move to a specific node directly, without traversing through the list.

For example, lets say the user wants me to move to the 4th node, and passes an int = 4 to the move function

Is there anyway that I can move directly to the 4th node without doing this:
for (int i = 1; i <=pos; i++)? Assuming that pos is the given argument

[JayhawkZombie]

Possible, yes. Easy? Not really.

We can do this with arrays because they are contiguous in memory. Linked lists do not make any guarantee about that. I've never a linked list be contiguous in memory.

This code will show the difference between them. Generally, for a linked list, traversing through isn't too expensive. It is a linear operation. If you are storing a huge amount of nodes, you might want to consider using a different data structure.

****I'm sorry if there's an error. It's late here. I've double-checked output, and it looks fine to me. I even counted the number of news and deletes.

#include <iostream>

struct myStructure
{
	int a;
	int b;
	double c;
};

struct linkedlistnode
{
	linkedlistnode *next;
};

int main ()
{
	myStructure myStruct[5];
	int index = 0;
	
	std::cout << "-------------Addresses for arrays-----------------" << std::endl;
	std::cout << "Address of myStruct[0] is: " << &myStruct[0] << std::endl;
	std::cout << "Input index (between 0 and 4)" << std::endl;

	std::cout << "Addresses of array indices are: " << std::endl;

	for (int i = 0; i < 5; i++)
	{
		std::cout << "\t&array[" << i << "]: " << &myStruct[i] << std::endl;
	}

	std::cout << "Enter an index: " << std::endl;
	std::cin >> index;


	if (index < 0 || index >= 5)
	{
		std::cerr << "Stop trying to break things." << std::endl;
		std::cerr << "But here's the address you requested: " << &myStruct[0] + 0x01 * index << std::endl;
		std::cerr << "Don't you dare write to that address.  It doesn't belong to you." << std::endl;
		exit(-1);
	}

	std::cout << "The address is: " << &myStruct[0]  + 0x01 * index << std::endl;// <-- Do this calculation in hexidecimal, not decimal

	std::cout << "-------------Addresses for linkedlist-----------------" << std::endl;

	linkedlistnode *list = new linkedlistnode; //Yay, dynamic allocation
	
	linkedlistnode *current = list;

	for (int i = 0; i < 5; i++)
	{
		current->next = new linkedlistnode;
		current = current->next;
	}

	current->next = nullptr;
	std::cout << "The addresses of the nodes are:" << std::endl;

	current = list;
	int nodeIndex = 0;

	while (current != nullptr)
	{
		std::cout << "\tlinkedlistnode[" << nodeIndex++ << "]: " << current << std::endl;
		current = current->next;
	}

	std::cout << "Enter an offset index (0 - 5): " << std::endl;
	std::cin >> index;

	if (index >= nodeIndex)
	{
		std::cerr << "STOP IT RIGHT NOW" << std::endl;
		std::cerr << "YOU GET NO ADDRESS" << std::endl;
		exit(-2);
	}

	std::cout << "Address of beginning of list: " << list << std::endl;
	std::cout << "Address of this index if contiguous in memory would be: " << list + 0x01 * index << std::endl;

	int counter = 0;
	current = list;
	while (current != nullptr && counter < index)
	{
		current = current->next;
		counter++;
	}
	std::cout << "Actual address is: " << current << std::endl;

	//cleanup
	current = list;
	linkedlistnode *temp;
	while (current->next != nullptr)
	{
		temp = current;
		current = current->next;
		delete temp;
	}
	delete current;
}

[alex067]

Traversing in a linked list is always O(n) isnt it? or is it log(n) depending on if you use a for loop or a while loop? Because you have to iterate through each element starting from the first, how can it be a constant run time?

[JayhawkZombie]

It's O(n). Using a for-loop or while loop shouldn't make a difference. Maybe using a for-loop could be better, because your compiler could unwrap the loops easily. But to do that you need to know the length of the list.
Thankfully, all you're really doing when you iterate to the next node is making yourself point to something else. It's not a very expensive process.
I wish it was linear. That would make it easier to calculate addresses. You can add to a linked list in constant time - just maintain a pointer to the current end of the list, attach to the end, and update the pointer to point to the new end of the list.