The tag has no usage guidance.

learn more… | top users | synonyms

0
votes
2answers
63 views

Correct way to implement linked list

I'm doing this challenge on Hacker Rank that wants me to implement a linked list. It seems to want me to find the last-added instance of node and change its head to link to my new instance of node. ...
2
votes
3answers
88 views

Why do we use multiple data structures? [duplicate]

I'm studying elementary data structures like Linked List, Doubly Linked List and Binary Trees like Binary Search Trees. Both runs in worst case O(n) in the same operations, so why don't we use only ...
0
votes
1answer
57 views

Recursive definition of Matrix

Like Linked-list for Array, is there a recursive counter-part for Matrix? Is there a persistent data structure which can be used in place of Matrix in pure functional language like Haskell?
10
votes
7answers
2k 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.
0
votes
0answers
15 views

Reverse linked list set logic in method B

I am trying to describe a reverse linked list in the B method. The structure I am trying to describe is below: F <- 1 <- 2 <- ... <- x <- L where ...
0
votes
0answers
54 views

Reverse linked listed — formal method?

I am trying to do some formal modeling of a linked list, however instead of referencing the next block, each block needs to reference the previous block instead. Is there already any formal methods ...
3
votes
0answers
75 views

Generalization of XOR Linked Lists

Are there any results generalizing XOR Linked Lists to other types of data structures? For example, just like an XOR Linked List requires two pointers and can iterate a 1 dimensional list, I can ...
3
votes
1answer
65 views

Best data structure for storing an ordered list, where each item is located on a separate server?

I need a structure that resembles an RSS feed of items, but each item is on a different network machine. Users cannot insert in the middle of the feed but only at its head. Deletions are possible. ...
1
vote
2answers
247 views

Why don't nodes carry as many pointers as possible in a skip list?

From this main picture explaining how skip lists work from Wikipedia, we see that some nodes carry different amounts of pointers to other parts of the list: Wouldn't it make more sense to have ...
1
vote
3answers
97 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 ...
2
votes
2answers
93 views

What is the trick used in skip lists to minimize $k + \frac{n}{k}$?

I was reviewing skip lists and the first step is to have two lists, the bottom one ($L_0$) of length n and the top one ($L_1$) of size k. Usually one traverses the "express line" (i.e. the top lane ...
3
votes
2answers
113 views

What is the average time complexity, for a single linked list, for performing an insert?

I thought this would be a very simple O(n) b.c. you can do the insert any where with in the list. The longer the list, the longer it will take on average to do the ...
-3
votes
2answers
98 views

If the list lengths are m and n, why does the merge take O(m+n) operations?

If I have two sorted lists. list A => 1 -> 2 -> 4 -> 11 -> 31 list B => 2 -> 31 -> 54 Now what should be the order of (sorted) merge and ...
6
votes
4answers
277 views

Order-preserving update of a sublist of a list of mutable objects in sublinear time

Description Say I have a source list like: ["a","b","c","d"] and want to run a capitalization filter so if I change, "b" to <...
6
votes
2answers
402 views

Is a stack machine with a forward read iterator Turing complete?

It is well known that a machine with a single stack as only unlimited storage is not Turing complete, if it can only read from the top of the stack. I want a machine which is (slightly) more powerful ...
1
vote
2answers
62 views

Why the pointer in linked list is of structure type? [closed]

Since any node points to a memory location is there any specific need in using it's pointer as structure type.Why couldn't we use integer as the pointer type in linked list rather than structure?
1
vote
0answers
545 views

Applications of Linked Lists [closed]

I tried looking in the internet but couldn't get any applications of linked list used in day-to-do life.Could anyone list any applications of linked list?
1
vote
2answers
252 views

Time complexity for searching $k-th$ element from starting and ending of a linked list

What are the time complexities of finding $8th$ element from beginning and $8th$ element from end in a singly linked list? Let $n$ be the number of nodes in linked list, you may assume that $n > 8$....
2
votes
1answer
296 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
33 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
18 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 ...
-3
votes
2answers
457 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?
1
vote
1answer
147 views

Does this algorithm on a circular linked list ever terminate?

Suppose we have a circular linked list that has nodes $1$ to $n$. L is a pointer that points to node 1 (with label $1$). Note <...
4
votes
2answers
224 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
51 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
36 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
145 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
189 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
76 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 ...
5
votes
3answers
2k 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
1answer
637 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
735 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
1k 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
4k 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 ...
9
votes
2answers
10k 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
158 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 ...