Questions tagged [linked-lists]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3
votes
2answers
134 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 ...
0
votes
1answer
19 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 ...
7
votes
3answers
729 views

Using singly linked list instead of a doubly linked list?

Are there advantages of implementing a singly instead of a doubly linked list other than space?
0
votes
1answer
30 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 ...
-1
votes
0answers
24 views

Linked List Algorithms

How to find middle element of a linked list using 1 stack or 2 stacks? I have tried using stack but unable. It is done using hare and tortorise pointers concept usually .
1
vote
1answer
26 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 ...
0
votes
1answer
62 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
0answers
24 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 (...
60
votes
6answers
51k views

Floyd's Cycle detection algorithm | Determining the starting point of cycle

I am seeking help understanding Floyd's cycle detection algorithm. I have gone through the explanation on wikipedia (http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare) I can see how the ...
1
vote
0answers
65 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 ...
0
votes
3answers
136 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 ...
1
vote
1answer
125 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$...
0
votes
1answer
212 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 ...
1
vote
1answer
52 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 ...
4
votes
3answers
9k views

What is the average time complexity, for a single linked list, for performing an insert?

I thought this would be a very simple O(n) b.c. you can do the insert any where with in the list. The longer the list, the longer it will take on average to do the ...
1
vote
4answers
4k 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 ...
-6
votes
1answer
321 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 ...
0
votes
1answer
423 views

How to get all in constant time?

We are planning to design a system where following operations are supported. ...
2
votes
1answer
21 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 ? (...
3
votes
2answers
268 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?
3
votes
1answer
90 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 ...
0
votes
0answers
39 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 ...
1
vote
0answers
26 views

Parallel deletion and traversal in a lock free linked list

I'm unsure about the safety of deletion in a linked list. I've seen the issue posed by a parallel insertion and deletion (resulting in the loss of the insertion) and proposed solutions to that problem....
1
vote
1answer
129 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 ...
4
votes
1answer
156 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 ...
7
votes
2answers
23k 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 ...
2
votes
1answer
73 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 ...
2
votes
1answer
112 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 ...
1
vote
1answer
32 views

A question about linked list

I would like to check the answer of this exercise: A circular doubled linked list with N elements has pointers that cost k bytes each of space in memory. How many bytes do the pointers of this list ...
3
votes
1answer
781 views

Recursive definition of Matrix

Like Linked-list for Array, is there a recursive counter-part for Matrix? Is there a persistent data structure which can be used in place of Matrix in pure functional language like Haskell?
0
votes
1answer
38 views

time complexity of erasing repeated entries

This problem involves the time complexity of erasing entries that occur more than once in a list. I think it might be $n \log n$. Problem The input is a finite set $S$ and a finite list $T$ ...
1
vote
0answers
40 views

Terminology Questions: Data-structure consisting of lists without repetitions

I've google around and have been unsuccessful in finding a name for a data-structure consisting of a list whose elements are unique. I've seen "unique sorted lists", but I'm looking into the more ...
3
votes
1answer
55 views

Why are linked lists considered O(1) for in-middle insertion/deletion whereas dynamic arrays are considered O(n)?

I am struggling to understand why linked lists seem to be accepted to have better big-O performance than arrays for in-middle insertion/deletion. The performance differences between lists and arrays ...
0
votes
1answer
59 views

Linked List fundamental concepts [closed]

I am trying to understand the basics of Linked List. The definition of my LinkedList class is as follows: ...
1
vote
2answers
272 views

What is the complexity of finding the predecessor of a node in a doubly linked list?

This is a question from Cormen 3rd edition(exercise 10.1). I am of the opinion that the complexity should be O(1), as we just have to look into the next pointer of the current node. But the answers ...
2
votes
1answer
91 views

Linked List in Maximal Scoring Subsequences Algorithm

For a project, I'm implementing the All Maximal Scoring Subsequences algorithm. In the analysis portion of the paper, it describes an optimization that makes the algorithm run in linear time. Namely, ...
0
votes
3answers
138 views

What is the only condition that would cause the Insert operation of a dynamic data structure to return a “data structure full” error?

I want to know where can I find some resources on this question, because, after researching for a day and half, I couldn't find information specific to my question. Can anyone help me answer my ...
0
votes
1answer
2k views

How to find middle element of doubly linked list using head and tail?

Is there a way possible to find the middle element of a doubly linked list using head and tail. I tried traversing to the next element from the starting node and the previous element from the end node ...
-2
votes
1answer
95 views

Learning to prove correctness of simple linked-list algorithms

I understand how to use linked lists, and build algorithm using them. But I don't understand how can we prove their correctness, even of simplest algorithm. I haven't even found a good tutorial ...
-1
votes
3answers
1k views

Finding the nth to last node in a linked list

I have a linked list with n elements and my goal is to find the 'nth to last element' in the list. I would like to present my approach. Please provide your opinions on whether it is optimal or how may ...
6
votes
5answers
2k views

What precisely/concisely is the “head” of a singly linked list? I ask bc of ambiguity online

So I have a pic which I think illustrates my confusion: the read surrounds what I wonder is the head? Does head refer to a node with both a data and next, or only a node with next? In other words, ...
0
votes
2answers
55 views

Is linked list a preferable underlying basic DS for a collection mutable through an iterator

I need to implement a collection DS that exposes an iterator which can be used to iterate an underlying collection and possibly remove the current item. I can use either a vector (dynamic array) or a ...
0
votes
1answer
215 views

Finding an element in a infinite unsorted doubly linked list

Is there any way to find an element in an unsorted doubly linked list given an element and pointer from which we can navigate? (we can't use head/tail pointers since the list is infinite)
0
votes
4answers
915 views

Finding the $k$th largest element in an unsorted array

What is the complexity of finding the k'th largest element in an unsorted linked list? If we sort the list, I think that the complexity is O(nlogn + k)=O(nlogn) since k < n. Is there a way of ...
1
vote
2answers
251 views

Linked lists in practice

I have some questions about the ideas proposed in this video. The speaker shows an array that holds values and pointers, and he also shows a separate "free" linked list, that is updated whenever an ...
1
vote
2answers
2k views

What's the advantage of two pointers linked list implementation of Queue versus one pointer circular list

Princeton Algorithms course shows the implementation of Queue using linked list and two pointers - head and tail. I've ...
0
votes
1answer
444 views

What is the type of linked list where order doesn't matter

I'm reading the The Algorithm Design Manual book on Data Structures and it says the following about linked listed implementation: Insertion into a singly-linked list is a nice exercise in pointer ...
0
votes
1answer
3k views

Insertion and deletion complexities for a linked list and array

I have the following table that compares different operation complexities for a linked list and array: ...
0
votes
1answer
346 views

What is `wasted space` parameter and why is it O(n) for a linked list

I'm reading a book on data structures and there is a comparison between linked list, array and dynamic array. The parameter name is wasted space. Here are the values: \begin{array}{cc} \text{...
0
votes
1answer
127 views

Given an algorithm, do worst case time complexity “class” vary with array and linked list?

My intuition says that I can make a sorting algorithm(may be a strange, not an useful), such that with array it have different worst case time complexity class and linked list(assuming time complexity ...