The tag has no wiki summary.

learn more… | top users | synonyms

4
votes
2answers
71 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?
1
vote
0answers
21 views

Declaring, changing, and adding to an array of a list of structs in C [migrated]

I've created a struct and the struct has a metric on it. I am generating a series of these structs and I want to sort them into an array based on this metric. Basically, if the metric is 0, I want it ...
-1
votes
1answer
30 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 ...
-1
votes
1answer
22 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 , ...
0
votes
1answer
128 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$. ...
1
vote
2answers
119 views

How to purge a linked list in $\mathcal{O}(n\log n)$ time?

I was wondering how to remove duplicate values from a linked list in $\mathcal{O}(n\lg n)$ time. I have an idea that by using merge sort when we want to compare elements for choosing the small one, if ...
0
votes
3answers
71 views

linklist and memory issues [closed]

I have a doubly link-list like this typedef struct Record { int i; Record* next; Record* prev; }Record; I have over 5 trillions of records that I need ...
4
votes
3answers
896 views

Maintaining an efficient ordering where you can insert elements “in between” any two other elements in the ordering?

Imagine I have an ordering on a bunch of elements like so: Where an arrow $X \leftarrow Y$ means $X < Y$. It is also transitive: $\left(X < Y\right) \wedge \left(Y < Z\right) \implies ...
5
votes
2answers
310 views

What linked list data structure adjustments would give me fast random lookup?

I am presently using an doubly linked list (C++ std::list) to hold a bunch of records that each have a unique integer identifier. The linked list is created in ...
1
vote
1answer
180 views

Selecting a node of a singly-linked list such that the probability of each node being selected is equal

The Question: You are given a singly-linked list with n nodes that you can only iterate through once at most. You are given additional space to store one node (i.e. a pointer to it). Devise an ...
1
vote
1answer
478 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 ...
5
votes
2answers
1k views

Implement queue with a linked list; why would it be bad to insert at the head and remove at the tail?

In my textbook, Data Structures and Algorithms in Java, the author says when implementing a queue using a linked list you choose the front of the queue to be at the head of the list, and the rear of ...
2
votes
0answers
4k 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 ...
10
votes
0answers
138 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 ...