Questions tagged [linked-lists]
The linked-lists tag has no usage guidance.
107 questions
0
votes
0
answers
23
views
Field from "dummy" node gets updated
I am trying to implement evenOddMerge solution to the problem (grouping together firstly odd indexed nodes, then even indexed nodes, e.g. from ...
- 103
1
vote
3
answers
84
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
816
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
124
views
1
vote
0
answers
69
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
653
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
71
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
42
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
70
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
173
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
134
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
198
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
2k
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
84
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
-1
votes
1
answer
4k
views
What are the time complexities of finding kth element from beginning and kth element from end in a doubly linked list
What are the time complexities of finding kth element from beginning and kth element from end in a doubly linked list? Assume n > k, where k is a constant and n is a total number of nodes in the ...
0
votes
3
answers
3k
views
Complexity of insertion into a linked list, single vs double
At https://www.javatpoint.com/singly-linked-list-vs-doubly-linked-list, it says:
In a singly linked list, the time complexity for inserting and
deleting an element from the list is O(n).
And:
In a ...
- 101
0
votes
0
answers
49
views
Applications of circular linked lists
Is a circular linked list just a nice programming exercise, or does it have any real world applications? I am unable to find much information on this topic, and any help would be appreciated.
- 339
2
votes
1
answer
31
views
Iteration over long linked lists and trees instead recursion
For example exist linked list with thousands (maybe million) elements or very deep tree which some branches are very long and have only one child, but exists other short branches with many children. ...
- 141
0
votes
1
answer
37
views
`STACK-FULL` and `QUEUE-FULL` with worst-case $\Theta(1)$
There are two problems in CLRS about implementing stacks and queues with singly linked lists. I know the solutions, I know how STACK-EMPTY and ...
- 421
1
vote
2
answers
277
views
Return Linked List elements as an array
Out of pure curiosity, if I have a Doubly Linked List, what would be the fastest way to return the elemenmts of the List in the correct order as an array? For example, would it be more efficient to ...
- 59
3
votes
1
answer
594
views
Algorithm to Compute High Water Mark
I saw this algorithm question which is as below.
There is a server that receives request Ids that are positive integers.
The High Water Mark (HWM) for the server at any instant of time is defined as ...
- 131
1
vote
1
answer
41
views
Measuring the length of a "loop" in a linked list in $O(n)$ Time?
I have been given a linked list in Python. At some point, one of the nodes is linked to a previous node creating a "tail" and a "loop":
Node1 -> Node2 -> Node3 -> Node4 -&...
- 113
1
vote
0
answers
53
views
Is a circular linked list (of a finite set of nodes) considered to be an infinite list?
So, a circular linked list is a linked list where the next pointer of the last node points to the first node (forming a circle).
Now, a linked list comes with some standard methods, like size()/length(...
- 111
0
votes
0
answers
251
views
Augment the tree data structure for disjoint sets to implement the PRINT operation
Consider the following new operation for disjoint sets
PRINT(x): print every element in S_x the set containing x
One Approach that I found but couldn't figure out completely :
In addition to tree we ...
- 131
0
votes
0
answers
208
views
Why is LRU cache not implemented using doubly linked list with just two nodes? Do we even need double linked list?
I don't understand why do we need to have more than two nodes in doubly linked list when all we need to maintain is the most recent and least recently accessed nodes.
I was going through solutions for ...
- 101
1
vote
1
answer
54
views
Why doesn't the assignment of processors contribute to runtime in a PRAM algorithm?
The following algorithm for computing the number of nodes in a linked list appears in this thesis on common algorithms in the PRAM model for parallel computation.
The author then argues that this is ...
- 363
4
votes
2
answers
257
views
Is there another type of list than arraylist and linked-list?
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 ...
- 185
0
votes
1
answer
278
views
LinkedList: Remove the kth node form the end
Question: Write a function that takes in the head of a Singly Linked List and an integer k and removes the kth node from the end of the list. The removal should be ...
- 101
1
vote
2
answers
235
views
walk / traverse a disjoint set that has union rank and path compression
I'm studying CLRS section 21.3, which introduces a union rank + path-compressed implementation of disjoint set. The implementations of MAKE-SET, UNION, LINK, and FIND-SET on p 571 of the book all work ...
- 858
1
vote
1
answer
61
views
Position in the Linked-list
I am reading Data Structures and Algorithms by Alfred Aho, Jeffrey Ullman, et al. In the section about lists it's said:
We should note that a position in a linked-list implementation of a list ...
user127304
1
vote
3
answers
2k
views
Floyd's Cycle Detection Algorithm Proof In Laymen
I came across the algorithm question of detecting a cycle in a linked list, but the solution has to be constant space O(1).
I have looked through various proofs proving that:
If there is a cycle, at ...
0
votes
0
answers
46
views
Number of complete traversals of the circle in generalised Josephus problem?
In the generalised Josephus problem, n people stand in a circle and every kth person is eliminated until only one person is left. The last person left standing can be found using dynamic programming (...
1
vote
0
answers
94
views
Trees with duplicate nodes and path cancellations
I have a bunch of objects that I am not sure on how to represent in order to maximize memory occupancy and possibly avoiding large CPU overhead. The most natural way to see the whole data structure is ...
- 111
0
votes
1
answer
648
views
Average number of inspections
Consider a set of n elements whose key values are $$0, 1, ..., n−1.$$ Let $p(i) (0 ≤ i ≤ n−1) $ be the probability that the element with key i is searched. Assume the following distribution of $p(i)’s$...
- 15
0
votes
1
answer
891
views
How To Merge Together Two Circular Doubly-Linked Lists In O(1) Time?
I'm implementing a Fibonacci Heap, where the lists are stored as a circular doubly-linked lists. What I'm trying to do is given a pointer to a random node in one linked list, and a random node in ...
- 117
1
vote
1
answer
76
views
Feeling guilt tripped in linked list
Okay, so I have been doing competitive programming for the past few days in C++. And day before yesterday, I stumbled upon this concept of linked list.
Now, what I do while implementing most ...
- 25
1
vote
4
answers
10k
views
Time complexity of insertion in linked list
Apologies if this question feels like a solution verification, but this question was asked in my graduate admission test and there's a lot riding on this:
What is the worst case time complexity of ...
- 530
-5
votes
1
answer
350
views
data structure linked list
Suppose as a computer programmer, you have been assigned a task to develop a program to store the sorted data in ascending order. Initially you have used linked list data structure to store the data ...
- 11
0
votes
3
answers
692
views
Is it possible to sort a linked list without copying its values but linking the nodes?
Is there an algorithm I could use when copying the values is not allowed? My list is going to be sorted in an ascending order.
Also can this be done in a quadratic time?
I will be attempting this in ...
- 21
2
votes
1
answer
206
views
delete node from linked list (lang w/GC) -should deleted item 'next' be set to null
Regarding: delete a node from a linked list algorithm,in procedural languages with garbage-collection.
Should there be a step in the algorithm, of setting the removed-node-next-pointer to null ?
(...
- 21
3
votes
1
answer
195
views
Why is LinkedList useful?
If you implement a stack with a dynamic array-based with LinkedList you need more memory than with a dynamic array, and with dynamic array for insert in amortized cost is O(1), so the advantage of the ...
- 33
0
votes
0
answers
135
views
Linked lists with auxiliary data
I'm trying to design a data structure that supports the following operations in $O(1)$ time:
$\operatorname{query}(\ell)$: Yield some auxiliary datum associated with list $\ell$ (just a single ...
- 227
4
votes
1
answer
387
views
Linked list: advantages of preventing movement of nodes and invalidating iterators on add/remove
C++ and Java include native classes for linked lists, C++ std::list and Java LinkedList
For C++ std::list, nodes can be "moved" within a list, or from list to list (if the lists are compatible), via ...
- 364
5
votes
3
answers
543
views
The origin of list data structure
Does anyone know when the list data structure was mentioned in computer programming/algorithms? Who gave birth to this list concept?
- 153
1
vote
1
answer
210
views
Linked List with Merge Sort [closed]
Is Merge Sort the best sorting technique to sort a linked list? Also, which sorting technique is worst for a linked list?
Merge sort uses a divide and conquer method. What makes merge sort efficient ...
- 153
9
votes
2
answers
76k
views
What is the time complexity of enqueue and dequeue of a queue implemented with a singly linked list?
I’m trying to understand the time complexity of a queue implemented with a linked list data structure. My book says that we can the implement a queue in O(1) time by:
enqueueing at the back
...
- 91
2
votes
1
answer
250
views
Sorting elements of linked list
I've been looking over sorting algorithms for linked list and here's what I came up with.
As we know, for element access arrays will work better than linked list. Also, there is the benefit of ...
- 41
2
votes
1
answer
565
views
Binary trees and preallocated nodes
I want to design a binary tree with preallocated nodes, in order to avoid calling malloc/free every time I want to insert/delete a node. The problem is I don't know ahead of time how many nodes the ...
- 208