Questions tagged [lists]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
1answer
25 views

Position in the Linked-list

I am reading Data Structures and Algorithms by Alfred Aho, Jeffrey Ullman, et al. In the section about lists it's said: We should note that a position in a linked-list implementation of a list ...
0
votes
3answers
69 views

What do you call a data structure containing multiple lists?

I was thinking about a data structure to make concatenation of lists easier, something that contains multiple lists (in a sequence) internally, but can be treated as a single contiguous list. I know ...
1
vote
2answers
44 views

A silly doubt on Computer Science Objects: Arrays, Lists, Strings, and Vectors, are they the same concept?

First of all I'm a Physics Student and I've been arguing with my brother concerning the usage and the fundamental meaning of a vector on Computer Science (CS). I) Vectors A vector have a axiomatic ...
0
votes
1answer
77 views

What is the difference between python list and c++ vector?

I read about the similarities between the python list and c++ vector and it looks as if the only difference is python list is heterogeneous. Are there any other differences? How are they both ...
1
vote
1answer
37 views

What is the theoretical result of flattening a list containing only itself?

Consider the following python code X = [None] X[0] = X This has many fun properties such as X[0] == X and ...
2
votes
1answer
16 views

Generate slice that contains element

Suppose I have the array: [2, 3, 4, 5, 6, 7, 8, 9] Now based on few parameters: current_item - currently selected item. <...
1
vote
2answers
49 views

What is the name of the data structure that is a tree on the backend but has a list like API?

I'm looking for the name of a data structure. It is organized like a balanced tree. The elements need not be comparable. Instead of asking if the tree contains a thing (like you would with a ...
0
votes
1answer
55 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 ...
1
vote
2answers
302 views

Sorting a large list of test scores

You have a large list (say N > 10000) of test scores which you would like to sort. The test scores are between 1 and 100. What is quickest way to sort the list? First thought. We have a O(N log N) ...
0
votes
1answer
124 views

Difference between a skiplist and an Indexable skiplist

Can someone please help me understand the main differences between a simple skiplist and an indexable skiplist? How does an indexable skiplist work in comparison to a normal skiplist (maybe a little ...
2
votes
2answers
122 views

Minimizing the iterative sum of pairs of numbers in a list

Given the tuple (list, value): $$\left(\left[x_1, x_2, \cdots x_n\right], y\right)$$ You may choose two adjacent values in the list to modify the tuple as: $$\left(\left[x_1, x_2, \cdots x_{i-1}, (...
0
votes
1answer
55 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
41 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.
3
votes
2answers
253 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
62 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
2k 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
140 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
130 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
155 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: ...
1
vote
0answers
215 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
43 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
31 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
40 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 ...
4
votes
1answer
170 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) ...
3
votes
1answer
430 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
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
0answers
114 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
9k 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
40 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
140 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
187 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
57 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
108 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?
17
votes
3answers
30k 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
63 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
75 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
101 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
419 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 ...
3
votes
3answers
1k 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
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
1answer
187 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
1answer
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
1answer
51 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
57 views

Can randomization be proven?

There exists a collection c where c = {1, 2, 3} and a randomization of c, ...
1
vote
0answers
48 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 ...
5
votes
2answers
5k 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
538 views

Skip List randomization complexity

I understand the basics of Skip Lists and their implementation also the basic Search Insert ...
2
votes
2answers
511 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
112 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 ...