The tag has no usage guidance.

73 questions
Filter by
Sorted by
Tagged with
47k 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 ...
13k views

### How to find middle element of linked list in one pass?

One of the most popular question from data structures and algorithm, mostly asked on telephonic interview.
223 views

### Is there a data-structure which is more efficient than both arrays and linked lists? [duplicate]

Background: In this question we care only about worst-case running-time. Array and (doubly) linked lists can be used to keep a list of items and implement the vector abstract data type. Consider the ...
5k views

51 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 ...
2k 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 ...
245 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 ...
193 views

### Usefulness of a linked list with a cycle

Is a singly-linked list that contains a cycle considered a corrupted data structure or is there some practical use for it? (You could argue that a car without its front shield is not corrupted, if ...
113 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 ...
28 views

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

### Order of storage of pointers for a linked list of length n

I have a linked list in which I have kept the elements in order (increasing/decreasing). I want to be able to perform a binary search on this linked list. For this I am keeping pointers to the middle ...
63 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 ...
25 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....
88 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 ...
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 ...
113 views

Let's say you have a standard doubly link list implementation: struct List { int Number; struct List *blink; struct List *flink; }; and that you have ...
5k views

### Complexity of algorithm inserting an element in a circular linked list at the front end

In a circular linked list, if an elements needs to be inserted at front [just before the node pointed by head], can be done in O(1) (see the answer here) But in a book currently, I have, it is ...