Questions tagged [linked-lists]
The linked-lists tag has no usage guidance.
106
questions
1
vote
3
answers
59
views
Can there exist a deque like data structure that supports amortized $O(1)$ random access?
A lot of modern languages usually have a "list" or "vector" structure which allows for amortized $O(1)$ append and removal from back as well as amortized $O(1)$ random access.
I'm ...
- 375
2
votes
5
answers
783
views
In-Place Reordering of Doubly Linked List Nodes to Ensure Memory Contiguity
I am addressing an optimization problem involving a doubly linked list, where nodes are allocated within a contiguous memory block of fixed size $N$. Initially, the spatial locality of nodes in memory ...
1
vote
1
answer
28
views
Linked Lists, Ordered Pairs?
I would like to model linked lists using set theory similar to that in Scheme and LISP.
There is a set theoretic definition of the ordered pair:
$p = \{\{a, 1\}, \{b, 2\}\}$
My question is how does ...
- 111
0
votes
2
answers
100
views
1
vote
0
answers
44
views
Is there an equivalent to "car" and "cdr" for "snoc"?
Note: This question assumes familiarity with cons-style linked lists (e.g., from Lisp or Scheme).
It also assumes familiarity with snoc-style lists. Snoc is like cons, except it appends elements to ...
- 111
0
votes
1
answer
486
views
Parallel Algorithm Pseudocode: Helman-JaJa Listrank
What would Helman-JaJa listrank pseudocode be like? I tried looking around but all I found were "prosecode" descriptions (eg pp. 18-19 here) which I find kinda hard to follow.
- 21
0
votes
2
answers
59
views
What are common heuristic algorithms of self-organizing list?
So in my "Advanced algorithms" course, we were taught about the "self-organizing list" data structure. The professor showed the following three heuristic algorithms: Frequency ...
- 223
-4
votes
1
answer
40
views
Data Structure And Algorithm
Given any singly linked-list L storing n real keys, that is, each key in L belongs to
R, design an algorithm (either in words or in pseudocode) that computes the sum of the negative keys in L. What is
...
- 1
0
votes
1
answer
59
views
Is returning pointers to nodes for a list (doubly linked list) implementation a leaky abstraction? and is it bad?
I've been studying closely about the List abstract data type - As I understand it can be implemented with linked-list and/or arrays, and really maybe with any other data types as well.
But to satisfy ...
- 133
0
votes
1
answer
128
views
Are linked lists homogenious or heterogenious containers?
I have always assumed that "Linked List" is something in the lines of
...
- 103
0
votes
0
answers
124
views
Slot implementation of LRU cache
Usually LRU cache is implemented with double linked list to fast remove oldest visited, push to front, and move from any place to front; also uses map to fast find element by key.
In 64bit systems ...
- 141
0
votes
1
answer
192
views
How to analyze the amortized running time of indexed linked list operations using potential method?
I have implemented an indexed linked list that runs (under mild assumptions) all single-element operations in $\mathcal{O}(\sqrt{n})$ time. The description is here and Java implementation is here.
It’...
- 52
6
votes
8
answers
4k
views
Advantages of linked lists over arrays?
Are there other advantages to linked lists over arrays other than constant time removals of the first element?
- 273
2
votes
1
answer
1k
views
Array vs Linked List Implementation of Stacks (in JS)
Let's say I want to make a Stack class in JavaScript. The class will have a push() and a pop() method. I have two options for ...
- 121
4
votes
1
answer
82
views
Copying a linked list with additional arrows from each node
Statement
Consider the following modified node structure for the linked list:
struct Node {
int value;
Node* next;
Node* random;
}
The ...
- 228