Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [lists]

The tag has no usage guidance.

0
votes
0answers
10 views

Most efficient way of converting lists of lists of variable length into np.array in python? [on hold]

What is the most efficient way to convert lists of lists of variable length into a np.array (3-dimensional matrix or n-dim matrix in general) in python?
0
votes
1answer
37 views

Lazy streams and infinite series

I just started Unix System Programming with Standard ML and starting on page 22 Shipman begins to explain a pure functional way of avoiding the constant state changes of typing at a keyboard: A ...
1
vote
1answer
24 views

What is an array that can be iterated circularly an infinite amount of times called?

I have a feeling that the answer is either a "circular linked list" or a finite state machine, but the answer is probably a circular linked list.
2
votes
1answer
175 views

The origin of list data structure

Does anyone know when the list data structure was mentioned in computer programming/algorithms? Who gave birth to this list concept?
1
vote
2answers
40 views

Lexicographic permutation list

Does anyone have an algorithm for stepping through all permutations of n given arbitrary objects in lexicographic order? Thanks.
2
votes
1answer
101 views

How to best maintain a sorted list from a stream of integers?

If I have an incoming stream of integers how can I best maintain a sorted list of them? The only way I can think of is to binary search for the position and shifting the remaining elements to the ...
1
vote
2answers
71 views

Algorithm/data structure to quickly check if an integer is a member of any [lower, upper] interval

Are there any existing algorithms/strategies to test if an integer value is within the bounds of any of a list of intervals, where each interval is denoted by a [min, max] pair? The naive approach is ...
0
votes
1answer
35 views

Parallel Algorithm for Data Averaging

I am trying to write an efficient Parallelised algorithm for Data Averaging. By this I mean I have a list of tuples (K, V1, V2, V3) and in the end, I want a dictionary mapping K to the average of all ...
6
votes
2answers
131 views

Can a list with $\mathcal{O}(1)$ access have an insertion complexity better than $\mathcal{O}(n)$?

It seems intuitive that there's no list data structure which has $\mathcal{O}(1)$ worst case time complexity for random access and a worst case complexity better than $\mathcal{O}(n)$ for insertion: ...
2
votes
0answers
54 views

Insertion in 123 skip list

I had a problem in my exam dealing with 1-2-3 skip lists. I have a problem with the insertion process in a 1-2-3 skip list. What I understand is that if the minimum of heights of 2 nodes in a 123 ...
1
vote
0answers
39 views

What is the most efficient algorithm for creating a list of unique values from a list of pairs of value?

Background I have a list of 50 million $A-A_i$ pairs, where $i>1$, and $A$ and $A_i$ are some text. I need to extract the $A$ values from the list, so I get a new list of unique $A$ values.: $$ \...
2
votes
0answers
39 views

Abstract Data Type

I have been studying data structures. In that I have come across topics like Array being defined as Power set of cross product of set of objects and set of natural number and list being defined as ...
1
vote
1answer
28 views

Abstract Data Types and their Implementation [closed]

I wanted to know if there is good resource to learn about the ADTs like set ADT, list, array, boolean etc and their implementation.
1
vote
0answers
36 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 ...
3
votes
1answer
58 views

Given a RxC grid, how to generate N 2D points randomly such that no 3 points are collinear?

Context, I have a geometric algorithm that is sensitive to collinear points and receives as input a list of points in 2D generated randomly. Suppose that I have a Boolean function nonCollinear(x,y,z) ...
2
votes
1answer
78 views

Fastest way to search a word in a word list?

I have a word list like "English Open Word List" used to create word games. The list is in txt file with space between words, like; aa aah aahed .........and so on. I want to search it while typing ...
0
votes
0answers
34 views

create distance (ment is high difference between values) between Vertexes in a list

Given are some vertexes, arranged in a list (so there every vertex is connected with two others and there are no circles in the graph). Every Vertex contains one number. Now you can lower the Number ...
0
votes
0answers
87 views

Big O Notation for Return List is it O(N)?

what is the Big O for Returning List? aka return list (e.g. list=[1,2,...]) is it o(1) or o(n) and is there a good website for average big o for different operations including sorting for simple ...
0
votes
2answers
3k views

Time complexity to check if there is an edge between two nodes in an adjacency list

I know that the time required to check if there exists an edge between two nodes in an adjacency matrix is $O(1)$ because we can access it directly (i.e: $M[i][j]$). However, I didn't really get why ...
1
vote
2answers
31 views

How would I go about determining popularity and relevance among articles and use it to improve my search algorithm

Disclaimer: First of all I've had a lot of trouble finding the right stack exchange site for this question and I don't know if it's correct here either. The Problem: I'm working on a search algorithm ...
0
votes
1answer
43 views

Remove duplicates of first elements of pairs

A list of pairs is given using Python. I want to remove duplicate occurrences of the first element of the pair leaving only one occurrence of each first element paired with the highest second element ...
0
votes
0answers
163 views

List of scheduling problems and their statuses

As of 1993, there are 4536 scheduling problems, 3821 were proven to be $NP$-hard, 417 polynomially solvable, and 298 still open. Where can I find the most up-to-date list of scheduling problems and ...
1
vote
1answer
50 views

Is there a name for the “tree” aproach to listing things?

I've only been studying computer science for a few weeks, so I apologize if this is a silly or naive question. Suppose we're trying to list all elements of the set $$C(r) = \{(x,y,z) \in \mathbb{N}^3 ...
1
vote
3answers
74 views

Partial intersection of 10 sorted lists of integers

Suppose I want to find the numbers that appear in at least 3 of the 10 sorted lists, is there an efficient way to do it apart from iterating over all 10 of them in parallel?
11
votes
3answers
14k views

When are adjacency lists or matrices the better choice?

I was told that we would use a list if the graph is sparse and a matrix if the graph is dense. For me, it's just a raw definition. I don't see much beyond it. Can you clarify when would it be the ...
2
votes
1answer
62 views

General name for linked lists based on hashes

I am thinking of a particular datastructure, but don't know the name of it. A sequence of elements may be modeled by a collection of some X, where each X consists of: The element, serialized as a ...
2
votes
1answer
64 views

Expected Time for LookUpSkipList

A skip list Let C(k) = the expected length of the path that raises k levels backwards. Thus C(0) = 0 For any node P in the path, with k levels higher to go, there are two cases: P is a node of ...
3
votes
2answers
98 views

Gauss-Jordan using stacks and list

I have a homework assignment in which I need to write an implementation of Gauss-Jordan with complete pivoting. Complete pivoting is a modification to the basic Gauss-Jordan algorithm in which rows ...
4
votes
1answer
337 views

How to use structural induction to prove law on lists

I want to prove that the following equation holds using structural induction on (finite) lists ...
4
votes
2answers
838 views

Why does linear search have $\frac{n}{2}$ comparisons on average?

I'm reading the Wikipedia page on Linear Search and it is mentioned that there are on average $\frac{n}{2}$ comparisons. I tried working this out on my own. First I considered the number of cases. ...
8
votes
4answers
3k views

What's the fastest way to find the Kth smallest value in an unsorted list without sorting?

My initial algorithm: Compare element 0 with every other element, keeping track of how many elements are less than it. Repeat for each element until an element that is greater than exactly (k-1) ...
0
votes
1answer
152 views

Efficiently finding duplicates in lists of numbers

I decided to try my hand at solving the knapsack problem. My idea involved generating $i$ tables, where $i: 1 \le i \lt n$, and each cell of an $i$ table contains one of the possible sums of the ...
2
votes
1answer
1k views

Lambda calculus lists construction explanation

I have the following notes that introduce how lambda calculus handles lists. They go as follows: A list is something we can match on and deconstruct if it is not empty: ...
3
votes
1answer
46 views

Description of lists with functions in LISP

I have been given the following implementation of basic list functions in LISP: ...
1
vote
2answers
5k views

Find out duplicate number between 1 to N numbers

I first saw this question on this website where I was trying on Java puzzles. Here is the Question:- ...
-1
votes
1answer
53 views

Can randomization be proven?

There exists a collection c where c = {1, 2, 3} and a randomization of c, ...
1
vote
0answers
46 views

Fastest way to Add and Subtract multiple parts of a List

I am doing some research where I have a List containing numbers. For example {5,10,98,22,13,15} What is a fast algorithm to calculate all possible sums and ...
3
votes
3answers
3k views

The fastest algorithm for intersection of two sorted lists?

Say that there are two sorted lists: A and B. The number of entries in A and B can vary. (They can be very small/huge. They can be similar to each other/significantly different). What is the known ...
3
votes
1answer
338 views

Skip List randomization complexity

I understand the basics of Skip Lists and their implementation also the basic Search Insert ...
2
votes
2answers
344 views

Find the duplicates in a list of floating point numbers

I receive a list of real numbers ( float ) between $0$ and $1$. The list has length $N+1$ and I need to find two numbers on the list which are $\le \frac{1}{N}$ ...
1
vote
1answer
76 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
138 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 ...
2
votes
0answers
94 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
113 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
252 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
22 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
73 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
588 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
372 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
668 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: ...