4
$\begingroup$

My question is not about how arraylists or linked-lists work, but why there aren't other types of lists.

From my understanding, memory is accessed linearly by adresses. Thus, you have the choice to use property for your list or not to.

In the case of a arraylist, you know where an item lies by looking where the element at index 0 is and then adding element-index x item-size, so you have constant access time.
For the case of a linked-list, you don't use the structure of memory and need to follow a sequence of pointers, but rearranging the list is easy.

Does this already explain why these 2 types of lists are all that's possible? Or is there another non-existence proof? Are there other types of lists I just don't know of yet?

Improve this question
$\endgroup$
1
$\begingroup$

A "list" or "sequence" is an ordered collection of elements.

So there are a lot of lists.

In addition to an Array and a Linked List:

Improve this answer
$\endgroup$
2
$\begingroup$

Yes, there are many types of lists depending on the arrangement of objects and the complexity of different types of operations. For example:

  1. Binary Tree or d-ary tree is a hierarchical structure that stores nodes in the form of parent and child nodes.

  2. Directed or Undirected Graph can be represented using adjacency list data structure which represents all possible connections between a set of objects. In other words, it is an array of lists.

  3. Doubly Connected Edge List is used for performing fast operations on planar graphs and 3-dimensional polytopes.

  4. Skip List is a randomized data structure that provides $O(\log n)$ insertion in a linked list

Likewise, you can even design your own data-structure based on different requirements. It is all about how you arrange and connect the objects.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ I will look into the last two suggestions. IMO, the first two don't qualify for lists. I would define a list as a function from 1,..,n to an arbitrary object type. A tree doesn't necessarily do that, except if it's one path, in which case it degenerated to a linked-list if you want to call it that way. $\endgroup$ – Moritz Groß Jan 16 at 15:35
  • $\begingroup$ @Morinator In that case, everything boils down to continuous or non-contiguous or partially contiguous set of memory locations. $\endgroup$ – Inuyasha Yagami Jan 16 at 15:41
  • 1
    $\begingroup$ For #2: "a graph can be represented using adjacency list". Yes, but I think OP is interested in the opposite: can a graph represent an ordered list? A set could also be represented by a list, but it doesn't help much. $\endgroup$ – Eric Duminil Jan 16 at 23:35
  • 2
    $\begingroup$ @Morinator: If you augment a balanced-binary-tree structure (such as a red-black tree or AVL tree) such that its nodes also store the size of their subtrees, then you can use that structure as a list in the sense you define. It provides logarithmic-time retrieval, replacement, insertion, and deletion, and linear-time iteration; so there are some operations that it performs better than an array-list and some that it performs better than a linked list. This approach is particularly useful when a purely functional list is desired. $\endgroup$ – ruakh Jan 17 at 0:05
  • $\begingroup$ @ruakh Ok that's what I'm talking about :) This idea reminds me of binary search, where you implicitly define a binary tree over the array by searching for the wanted element. $\endgroup$ – Moritz Groß Jan 17 at 0:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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