patternMinor
Is there another type of list than arraylist and linked-list?
Viewed 0 times
thantypeanotherandlisttherelinkedarraylist
Problem
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?
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?
Solution
Yes, there are many types of lists depending on the arrangement of objects and the complexity of different types of operations. For example:
-
Binary Tree or d-ary tree is a hierarchical structure that stores nodes in the form of parent and child nodes.
-
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.
-
Doubly Connected Edge List is used for performing fast operations on planar graphs and 3-dimensional polytopes.
-
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.
-
Binary Tree or d-ary tree is a hierarchical structure that stores nodes in the form of parent and child nodes.
-
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.
-
Doubly Connected Edge List is used for performing fast operations on planar graphs and 3-dimensional polytopes.
-
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.
Context
StackExchange Computer Science Q#134428, answer score: 2
Revisions (0)
No revisions yet.