We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [linked-lists]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
8
votes
3answers
5k 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 \left(...
2
votes
1answer
3k views

How is the directory implementation done using a linear list?

I am reading Operating System Concepts by Silberchatz, Galvin, Gagne and they write that a directory can be implemented using a linear list. [pg 470, 8th ed] However, I visualize directories as a ...
1
vote
0answers
108 views

Terminology for a partially unlinked doubly linked list?

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 ...
1
vote
2answers
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 ...
-2
votes
2answers
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?
6
votes
2answers
549 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
votes
1answer
92 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
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 , ...
0
votes
1answer
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$. ...
1
vote
2answers
289 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
80 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 ...
2
votes
1answer
1k 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 ...
6
votes
1answer
1k 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
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 ...
6
votes
2answers
11k 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 ...
10
votes
0answers
221 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 ...