2022 Developer Survey is open! Take survey.

# Questions tagged [lists]

The tag has no usage guidance.

78 questions
Filter by
Sorted by
Tagged with
0 votes
0 answers
94 views

### Design a data-structure $BankAccount$ that supports the following operations in constant time complexity

Problem: Design a data-structure $BankAccount$ that supports the following operations in $\underline{\text{constant time complexity}}$. Meaning $O(1)$. $Init()$ - initializes bank account $L$ with ...
1 vote
1 answer
36 views

### Why doesn't this implementation of Skip List simply return the current node when its key is equal to the query key?

I was studying Skip Lists in section 3.10 of Advanced Data Structures by Peter Brass and was confused about a detail of how the search algorithm in implemented. (This is self-study, not homework). The ...
0 votes
0 answers
24 views

### Good sources that treat "sliding window" whiteboarding-style problems?

This is a reference request for algorithms textbooks that address the common "sliding window" problems that come up in whiteboarding. If not textbooks per se, I'm looking for a more ...
4 votes
3 answers
397 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
0 answers
24 views

### Finding max values at a point given a list of ranges

In coding competitions I usually see problems that involve dealing with values in given ranges. A typical example is, given a list of 3-tuples defined as so ...
1 vote
1 answer
66 views

### Historical examples of bad security policies/mechanisms that we got stuck with through switching costs?

The following process seems to be a recurring one: Initial design. Commercial organisations invent and implement a design that seems at the time to work. Problem discovered, new design suggested. Due ...
4 votes
2 answers
187 views

### Is there another type of list than arraylist and linked-list?

My question is not about how arraylists or linked-lists work, but why there aren't other types of lists. From my understanding, memory is accessed linearly by adresses. Thus, you have the choice to ...
1 vote
1 answer
972 views

0 votes
1 answer
90 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
1 answer
57 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.
1 vote
2 answers
110 views

### Lexicographic permutation list

Does anyone have an algorithm for stepping through all permutations of n given arbitrary objects in lexicographic order? Thanks.
1 vote
2 answers
267 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 ...
2 votes
1 answer
3k 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 ...
0 votes
1 answer
312 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
2 answers
207 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
0 answers
48 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
1 answer
36 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
0 answers
46 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 ...
5 votes
1 answer
386 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) ...
0 votes
2 answers
14k 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 ...
3 votes
1 answer
818 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
0 answers
42 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
0 answers
170 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 ...
22 votes
3 answers
39k 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 ...
1 vote
2 answers
42 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
1 answer
286 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
0 answers
200 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
1 answer
64 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 ...
2 votes
1 answer
69 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 ...
1 vote
3 answers
120 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?
2 votes
1 answer
79 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
2 answers
105 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
1 answer
506 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 ...
8 votes
4 answers
4k 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
1 answer
206 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 ...
3 votes
1 answer
2k 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: ...
4 votes
1 answer
56 views

### Description of lists with functions in LISP

I have been given the following implementation of basic list functions in LISP: ...
1 vote
2 answers
6k 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
1 answer
59 views

### Can randomization be proven?

There exists a collection c where c = {1, 2, 3} and a randomization of c, ...