The Stack Overflow podcast is back! Listen to an interview with our new CEO.

The tag has no usage guidance.

65 questions
Filter by
Sorted by
Tagged with
320 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$ ...
45 views

I am trying to understand the basics of Linked List. The definition of my LinkedList class is as follows: ...
816 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: ...
90 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 ...
29 views

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 ...
249 views

How to get all in constant time?

We are planning to design a system where following operations are supported. ...
182 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$. ...
55 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 , ...
91 views

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

How efficiently can a doubly linked list be sorted? The minimum I could get is $O(n^2)$. Can anyone suggest something better?