0
$\begingroup$

I have always assumed that "Linked List" is something in the lines of

struct Node
{
    SomeClass payload;
    Node * next = nullptr;
    Node * prev = nullptr;
}

This implies the restriction of working with objects of only one type. Considering lists are horrible in access time I doubt anyone really constructs them on the stack. Arrive the conclusion that each node could be of different size. This probably possible with std::any. But in pure C one would need an additional redirect void * payload; or to loose type safety by converting the whole Node * to void *. In other words: possible but difficult.

Is there some inherent characteristic of lists which mandates they be as restricted as arrays or am I observing pure coincidence?

$\endgroup$
4
  • $\begingroup$ What is the connection between access time and stack allocation ??? $\endgroup$
    – user16034
    Commented Sep 19, 2022 at 12:17
  • 1
    $\begingroup$ IMO, this limitation is more due to the definition of pointers, which are statically typed. $\endgroup$
    – user16034
    Commented Sep 19, 2022 at 12:18
  • $\begingroup$ "Considering lists are horrible in access time I doubt anyone really constructs them on the stack." Depends on the implementation. You can use an array to implement a list where pointers are merely indices. $\endgroup$
    – Rinkesh P
    Commented Sep 19, 2022 at 17:05
  • $\begingroup$ Depends on your definition of homogeneous and heterogeneous, possibly on your implementation/a programming languages specification of list. $\endgroup$
    – greybeard
    Commented Sep 20, 2022 at 4:48

1 Answer 1

3
$\begingroup$

You say "linked list" without mentioning a computer language.

First, a "Node" is not a linked list. It is a helper struct that may be useful to create a linked list, but it is just a wrapper around some thing with additions so it can be made part of a linked list.

In Objective C or in Swift, you'd declare Node as something based on SomeClass, say in Swift struct Node { ... }. An important change that you would make: You'd put the two Node* first. That's because this means the Node* are always at the same offset; there will be many situations where the generated code will be identical for different classes, and Swift guarantees that code is not duplicated in such a situation.

In both languages, you can also declare the payload to be of type "id" in Objective-C, or "kindof whatEverClass" in Objective-C, or "Any" in Swift. In that case the payload can be anything (including different types) in Swift, and any object pointer, or any subclass of whatEverClass in Objective C.

In general, if you want a class "linked list", you just make sure it implements what is needed, like first, last, next, previous, insert, remove, lookup. The implementation is up to you. If I had to implement it for general use, I'd probably implement it using a series of arrays. So if you start with an empty list, one array would be allocated if you only add elements and remove items at the start or the end of the list. Operations in the middle of the list could allocate a second array. For the user, it would behave like a linked list, just more efficient then a naive linked list.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.