Verkettete Listen

[obi68]

Liebe community,

ist eine verkettete Liste mit unterschiedlichen Container-Inhalten überhaupt möglich?

Inhalt: Byte
Zeiger: Byte

später bei Dez 255 (max Wert für Byte)

Inhalt: Byte
Zeiger: Integer

und dann bei 256

Inhalt: Integer
Zeiger: Integer

Nur so könnten sämtliche Zahlen ob sehr klein oder sehr gross mit kleinst möglichen reservierten Speicherplatz in eine verkettete Liste gebracht werden.

Oder hat jemand eine ganz andere Methode bzw. Idee?

Besten Dank

Nachträge:
Die Sprache ist mir egal.
Arrays sind nicht dynamisch.
Es müssen auch Werte grösser int64 abgespeichert werden können.

 

[c0mp4ct]

Um welche Programmiersprache handelt es sich denn?

Falls es um C oder C++ geht ist das mit Hilfe von void Zeigern problemlos möglich.

Wenn dir die Sprache egal ist, dann hier ein Beispiel:

struct node {
	struct node *left;
	struct node *right;
	void *data;
};

 

[Fortatus]

Also 1. solltest du eigentlich keine verkettete Liste benutzen. Arrays sind schneller.
2. Zeiger sind von der Hardware abhängig. Auf 32Bit CPUs sind Zeiger 32Bit=4Byte lang, auf 64Bit CPUs=8Byte.
und 3. ist es nicht schlau für 255 Elemente und dabei 255*3Byte= 765Byte= 0,74kByte so einen Aufwand zu betreiben.

 

[antred]

Die Sprache ist mir egal.

Dir vielleicht, aber um diese Frage auch nur im Ansatz sinnvoll beantworten zu können, spielt die jeweilige Sprache eine entscheidende Rolle.

 

[kuddlmuddl]

Schonmal über OOP bzw. Vererbung nachgedacht?
Die Liste nimmt die Oberklasse auf und die Elemente können dann von einem von mehreren abgeleiteten Typen sein

 

[Fortatus]

Die Sprache ist mir egal.
Arrays sind nicht dynamisch.
Es müssen auch Werte grösser int64 abgespeichert werden können.

Dann nehmen wir C++:
Der Standardcontainer Vector ist prinzipiell ein Array. Und trotzdem gibt es die Funktionen push_back und insert. Mal aus einer Onlinequelle:

Vector containers are implemented as dynamic arrays

bzw.

Ein Vector ist ein dynamisches Array. Vector haben anders als statische Arrays keine feste Größe, sondern passen sich der Anzahl der Elemente dynamisch an.

(Quelle)
Habe ich vorher zwar nicht explizit gesagt, aber Vector sind in C++ dynamische Arrays. C++ <3 Für andere Sprachen: http://en.wikipedia.org/wiki/Dynamic_array#Language_support

Und wenn Werte größer also 64Bit gespeichert werden müssen, dann ist diese "Optimierung" ohnehin hinfällig. Daten in Objekte packen und die Objekte in den Container. Der Container ist eine abstrake Datenklasse, wird vllt. nur noch über Zeiger/Referenzen in den Container eingebettet; und anderenfalls ist er selber für den belegten Speicher zuständig. Da ist nichts mehr im Container zu optimieren.

 

[antred]

Liebe community,

ist eine verkettete Liste mit unterschiedlichen Container-Inhalten überhaupt möglich?

Inhalt: Byte
Zeiger: Byte

später bei Dez 255 (max Wert für Byte)

Inhalt: Byte
Zeiger: Integer

und dann bei 256

Inhalt: Integer
Zeiger: Integer

Nur so könnten sämtliche Zahlen ob sehr klein oder sehr gross mit kleinst möglichen reservierten Speicherplatz in eine verkettete Liste gebracht werden.

Oder hat jemand eine ganz andere Methode bzw. Idee?

Besten Dank

Nachträge:
Die Sprache ist mir egal.
Arrays sind nicht dynamisch.
Es müssen auch Werte grösser int64 abgespeichert werden können.

Hauptaugenmerk auf den rot markierten Teil. In diversen Sprachen mit dynamischer Typisierung (z.B. Python) kannst du in eine Liste schmeißen, was immer du möchtest. An den ersten Index einen Integer, an den zweiten eine Instanz irgend einer Klasse und an den dritten ein String? Kein Problem einfach rein damit.
ALLERDINGS, deine Anforderung für "kleinst möglichen reservierten Speicherplatz" geht bei Nutzung solcher Sprachen ohnehin flöten, denn im Vergleich zu C und C++ würde jedes Listenelement einen gewissen Overhead mit sich bringen (je nach Implementierung).


Wenn wir annehmen, daß sich deine Frage auf C++ bezieht, fallen mir nur 3 mögliche Ansätze ein, und keiner von denen ist besonders elegant oder auch nur im Ansatz effizient.

1) Du speicherst in einem std::vector nix als void-Pointer. Dann mußt du aber immer wissen, welchen Typs das über den jeweiligen Zeiger referenzierte Objekt ist. Dieses Wissen müßtest du natürlich selbst irgend wo hinterlegen, weshalb sich's auch hier mit der angeblichen Effizienz eigentlich schon gesch****en hat.

2) Du erstellst dir eine union und gibst der union als Member Variablen aller möglichen Typen, die du speichern möchtest. Dann legst du dir einen std::vector an, der Variablen des eben definierten union-Typs speichert. Das birgt aber das gleiche Problem wie 1).

3). Du benutzt die boost-Libraries und verwendest Boost.Any ... habe ich noch nie gemacht - kann daher nicht beurteilen, wie effizient das ist. Da die Boost-Leute aber auch keine Zauberer sind, nehme ich an, das diese Lösung eben so einen gewissen Overhead mit sich bringt, der deine Forderung nach maximaler Effizienz zunichte macht.


Ich würde noch mal gründlich hinterfragen, WARUM du solch eine Lösung überhaupt anstrebst. Aus meiner Erfahrung ist es eigentlich so gut wie nie notwendig, Objekte x verschiedener Typen in einem Container zu speichern.


EDIT: Zusätzlich könntest du natürlich noch eine komplexe Klassenhierarchie aufbauen und immer nur Zeiger des Basisklassentyps im vector speichern. Aber auch das bringt nicht die von dir geforderte Effizienz.