The tag has no usage guidance.

74 questions
Filter by
Sorted by
Tagged with
91 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 ...
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 ...
119 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 ...
213 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)
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 ...
377 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 ...
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$ ...
53 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: ...
889 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 ...
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: ...
111 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 ...
184 views

### Impact on the order of elements on the cost of searching in a linked list

I have the following homework question that I am struggling with. I have read the corresponding chapter from the book, but no guidance there. Consider a linked list $X: X_1 \to X_2 \to X_3 \ldots$. ...
15 views

### Trees with duplicates 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 it is as a tree. A picture ...
121 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$...
33 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 ...
364 views

### How to get all in constant time?

We are planning to design a system where following operations are supported. ...
60 views

### How to tell which value belongs to the key during hashing

To prevent collisions in Hash table , seperate chaining with linked list is used . Hash table works by hashing the key and storing the value in the bucket. Assuming 4 keys hash to the same bucket , ...
94 views

### Linked list implementation problem [closed]

Note its not a homework question, just practice Hi i have always seen linked list implementation in java using the following piece of code ...
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 ...
2k views

### Sort doubly linked list efficiently

How efficiently can a doubly linked list be sorted? The minimum I could get is $O(n^2)$. Can anyone suggest something better?
74 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 ...
19 views

### Problem to Insert at n-th position in a singly circular linked list of integers [closed]

Here's my code to insert a node at n-th position in a singly circular linked list. When tail is NULL , I'm trying to just return but that gives me a run time error. For this particular code, I am ...