The tag has no usage guidance.

learn more… | top users | synonyms

1
vote
1answer
44 views

Are there data structures that mix a tree structure with lists?

I suppose something like this could probably be easily designed, however I was wondering if there's a data structure that somehow uses both list and tree to access data. Something like this (I'll be ...
2
votes
2answers
77 views

How can I get O(1) prepend on a random-access list?

I need a data structure that has the following operation: $\operatorname{prepend}([x_{n - 1}, ..., x_0], x_n) = [x_n, ..., x_0]$ $\operatorname{prepend}$ should be in $O(1)$. Assume that you have ...
3
votes
0answers
89 views

How do I merge these lists?

I ave a a collection of lists of objects: $a_1$ $a_2$ $a_3$... $b_1$ $b_2$ $b_3$... $c_1$ $c_2$ $c_3$.. I need to merge them into a minimal possible number of lists, each list must be as long as ...
3
votes
1answer
25 views

Algorithm for grouping identical neighbors in a list

I have a list that I want to reduce to a smaller list by grouping identical neighbors. This list has many many redundant entries. Example list: ...
1
vote
2answers
89 views

How do I interpret this divide and conquer algorithm for removing duplicates in a list?

Consider the following divide and conquer algorithm to remove duplicates in a list. The text is in French. What is the meaning of the variables $c1, c2, d1, d2$? Why are only the variables $c1, d1$ ...
0
votes
0answers
31 views

What is a pair list?

From Ma, Introduction to theoretical computer science (Hsi-wen, and Xiwen Ma. Vol. 23. World Scientific, 1990), the authors state in Section 2.3.5, (1) An S-expression $x$ is said to be a pair, if $...
0
votes
0answers
15 views

Look for a pair of elements closest to two start positions in both directions until a condition is met

For a list which contains a set of elements I have two starting positions pos1and pos2 that are selected randomly. Next, I check ...
1
vote
0answers
38 views

What is this GlueList Data Structure?

I came across a new list data structure called GlueList that claims faster than classic list implementations. How does it work ? How can it be faster than ArrayList and LinkedList ?
1
vote
1answer
66 views

Creating a list of minimum-distance pairs from two lists

Let's say there are two lists of objects, list1 and list2, and that there is a function that can generate the "distance" between an object in list1 and an object in list2. What I would like to do is ...
6
votes
4answers
278 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 <...
0
votes
1answer
197 views

Structural induction over list

I want to prove that unique(reverse(L)) = reverse(unique(L)) where L is a List. List has the following constructors: ...
-1
votes
1answer
46 views

Operation with same asymptotic cost on hash tables and lists [closed]

Let $x \in \{ \log n, n, \dots , n!\}$ some (cost) function. Are there interesting operations with runtime in $O(x)$ on lists which also have runtime in $O(x)$ on hash tables?
0
votes
1answer
56 views

How to write all $r$-tuples with a certain property in a list [closed]

I have the following question: Let $a,b,c,d$ be four natural numbers with $a \leq b$ and $c\leq d$. I have written a program that produces a list, which has as entries all 2-tuples $(x,y)$ with $x\...
4
votes
3answers
151 views

counting arithmetic progressions $a, a+r, a+2r$ in a list

I have a large list $L$ of numbers and I need to count instances of elements $a,b,c \in L$ such that $a +c = 2b$. A brute-force approach would be to check all possible triples $(a,b,c)$ and this will ...
3
votes
1answer
113 views

Finding number not in list with wildcards

I have a list like this: 1*0*0 1**0* 0*0** 001** Where the number of elements in each row is $n$ and * is a wildcard for 0 or 1. I need a polynomial-time ...
0
votes
1answer
35 views

Join large list of pairs

I have a list of millions of pairs of strings, and I want to join all of the pairs that have matching members into lists without duplicates. Example input: ...
2
votes
2answers
205 views

Lazy lists with call-by-value reduction strategy

I am currently writing lists with lazy semantics in the pure lambda-calculus with call-by-value reduction strategy. I tried to construct pleasant to use and relatively efficient "lazy" functions on ...
5
votes
2answers
407 views

More efficient algorithm for determining if one list is a sublist of another list

I'm trying to build an algorithm which takes two lists of natural numbers and finds if every element of the first list is displayed at least once in the second list. What if the list is sorted? An ...
-1
votes
2answers
80 views

Counting occurrences of one vector inside another

I am asked to check if a vector contains another vector as a subvector. For example: $$v_1 = (4, \underline{3, 4}, 9, 10, 28, 5, 12, \underline{3, 4})$$ $$v_2 = (3, 4)$$ The answer here will be two, ...
2
votes
1answer
222 views

Skip lists with limited height

This is homework, so please only hints. I didn't want to put this on StackOverflow since this is mostly about theory, and SO gets inundated with too many questions. I am asked to find a method of ...
2
votes
0answers
80 views

Does a function distribute over lists or does it commute with them?

Assume that we have an operation $f$ such that $$ f([a_0,\ldots, a_n])= [f(a_0),\ldots,f(a_n)] $$ Do we say that $f$ distributes over lits or do we say it commutes with lists? Which one is the ...
5
votes
2answers
126 views

Longest subsequence such that A[i].x < A[i+1].y

I have an issue for which I am looking for an algorithm (if it exists) What I have: An array of items which have certain properties, e.g. item $A$ has properties $x$ and $y$. Example: $[ A(x,y), B(x,...
6
votes
1answer
103 views

Is there a term for the general method used in XORed linked list?

The XOR linked list is perhaps the most prominent example of storing a reversible hash of two values and using a known value and the stored hash value to derive the other value. Is there a term for ...
4
votes
1answer
4k views

Constructing of Double Connected Edge List (DCEL)

For a given planar graph $G(V,E)$ embedded in the plane, defined by list of segments $E= \left \{ e_1,...,e_m \right \} $, each segment $e_i$ is represented by its endpoints $\left \{ L_i,R_i \right \}...
4
votes
1answer
386 views

Building ideal skip lists

I'm trying to find the best algorithm for converting an “ordinary” linked list into an “ideal" skip list. The definition of an “ideal skip list” is that in the first level we'll have all the ...
5
votes
3answers
6k views

Quicksort vs. insertion sort on linked list: performance

I have written a program to sort Linked Lists and I noticed that my insertion sort works much better than my quicksort algorithm. Does anyone have any idea why this is? Insertion sort has a ...