Cursor-Implementierung: Element hervorholen, wie?

[Stussy]

Hallo,

ich grüble grade darüber nach, wie bei einer Cursor-Implementierung einer linearen Liste ein gewünschtes Element hervor geholt werden kann. Das geht doch nur, wenn durch die Liste laufe und den entsprechenden Index suche oder der Verkettung folge oder? Da hab ich doch für jeden Zugriff eine Laufzeit von mindestens O(n)!?

Nachfolgend das C++-Template zu meiner Test-Implmentierung. Ich verwende zwei Arrays. Das eine enthaelt alle Daten und das andere den entsprechenden Cursor auf das nachfolgende Element (ist das korrekt so oder macht man das anders?):

template <class T>
class CursorList {

private:
	// Enthaelt alle Atome
	T *atomList;

	// Enthaelt die Position der Nachfolger der Atome
	int *cursorList;

	// Die groesse der Liste
	int size;

public:
	CursorList(int size);
	~CursorList();

	void setAtom(int index, T *atom);
	void removeAtom(int index);
	T* getAtom(int index);
}

PS: Darauf aufsetzend möchte ich später noch eine Freispeicherverwaltung implementieren. Jetzt geht es mir jedoch primär um das Hervorholen eines Elements aus der Liste.

Vielen Dank.

Grüsse
Stussy