58 votes

Floyd's Cycle detection algorithm | Determining the starting point of cycle

I have seen the accepted answer as proof elsewhere too. However, while its easy to grok, it is incorrect. What it proves is $x = z$ (which is obviously wrong, and the diagram just makes it seem ...
l8Again's user avatar
  • 681
24 votes

How to find middle element of linked list in one pass?

By cheating, and doing two passes at the same time, in parallel. But I do not know whether the recruiters will like this. Can be done on a single linked list, with a nice trick. Two pointers travel ...
Hendrik Jan's user avatar
  • 29.8k
19 votes

Advantages of linked lists over arrays?

Linked lists can work well even if memory is fragmented. Arrays usually require a continuous piece of memory. For large piece of data finding this large continuous piece of memory might be hard. Most ...
Surprised Seagull's user avatar
17 votes

What is the time complexity of enqueue and dequeue of a queue implemented with a singly linked list?

Enqueueing You don't need to traverse the entire list to find the new tail, you just need to add a new node where the current tail points to and set that node as the new tail. Pseudocode (assuming ...
Adnan's user avatar
  • 315
9 votes

Advantages of linked lists over arrays?

This isn't really about "advantages", but appropriateness. Sometimes it's more appropriate to use an array, and sometimes to use a linked list. If it helps, take a look at this large table ...
Pseudonym's user avatar
  • 21.6k
8 votes
Accepted

The origin of list data structure

Knuth gives a good overview on the history of lists and linked data structures. From The Art of Computer Programming, Volume I, Section 2.6: Linked memory techniques were really born when A. Newell,...
Marcus Ritt's user avatar
7 votes

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

Either if you want to insert at the end of the list or at the beginning of the list, you're going to have $O(1)$ Complexity for that and $O(1)$ space. If you want to insert at the beginning of the ...
Ganea Dan Andrei's user avatar
7 votes
Accepted

Recursive definition of Matrix

Multiple Dimensions For a recursive counterpart for matrices, we need dependent types. Indeed, lists are one dimensional and so (horizontal) concatenation of lists is all that is needed. However, ...
Musa Al-hassy's user avatar
7 votes

How to find middle element of linked list in one pass?

If it's not a doubly linked list, you could just count and use a list, but that requires doubling your memory in the worst case, and it simply won't work if the list is too large to store in memory. ...
00500005's user avatar
  • 247
6 votes

How to find middle element of linked list in one pass?

Elaborating on Hendrik's answer If it's a doubly linked list, iterate from both ends ...
00500005's user avatar
  • 247
6 votes
Accepted

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

In the usual way, where each node carries $i$ pointers with probability $2^{-i}$, the average node has size $O(1)$, so the total space used by the skip list is $O(n)$. If each node carried pointers at ...
jbapple's user avatar
  • 3,310
6 votes

What precisely/concisely is the "head" of a singly linked list? I ask bc of ambiguity online

You're right, there are many different definitions of a List/Linked List. No one definition is correct nor incorrect. This answer is a bit long-winded, but having a backstory on the logic behind lists ...
ryan's user avatar
  • 4,431
5 votes
Accepted

Does this algorithm on a circular linked list ever terminate?

The algorithm will always terminate. Look at the case where $n=2$. Initially we'll have 1->next = 2 and 2->next = 1. In ...
Rick Decker's user avatar
  • 14.8k
5 votes

Floyd's Cycle Detection Algorithm Proof In Laymen

The easiest way to understand this is really to draw it out and move your fingers on a graph, so I recommend literally pulling out a piece of paper to follow along. Picture the part before the cycle ...
Zachary Vance's user avatar
5 votes

Advantages of linked lists over arrays?

If you make the elements stored in the list already contain the next/prev pointers (called an intrinsic or intrusive linked list) than the list doesn't need to do allocations and risk fragmenting ...
ratchet freak's user avatar
5 votes

Advantages of linked lists over arrays?

An important consideration missing from the other answers: It's easier and more performant to use immutable linked lists than immutable arrays, which is especially important in functional programming ...
markasoftware's user avatar
4 votes

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

And how would you like to manage this? It will resemble a tree, not skip list, and memory overhead will be bigger. Traversal time will decrease in some cases, but insertion time will increase. ...
Evil's user avatar
  • 9,425
4 votes

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

If you have no additional requirements on the contents of the list, you can just insert the item at the head, which is O(1). If you do (e.g. the list must be kept sorted or deduplicated), insertion ...
reinierpost's user avatar
  • 5,359
4 votes
Accepted

Correct way to implement linked list

First of all, don't have a head pointer in your structure that doesn't point to the head of the list: it will confuse everyone. Call the pointer in your structure <...
Martin Kochanski's user avatar
4 votes

Linked list: advantages of preventing movement of nodes and invalidating iterators on add/remove

I think this is due to the differences in the philosophy underlying the design of both programming languages. The C++ philosophy allows data structures to cause undefined behavior as soon as the user ...
chi's user avatar
  • 14.4k
4 votes
Accepted

Measuring the length of a "loop" in a linked list in $O(n)$ Time?

There is a surprisingly simpler solution! Are you familiar with the tortoise and hare algorithm? Start thinking from there: Understand this algorithm and why it works, and then you might get an idea ...
nir shahar's user avatar
  • 11.5k
3 votes
Accepted

Why do we use multiple data structures?

Aspects other than asymptotic worst case time are also important. For example Actual speed in practice Memory consumption Implementation difficulty Algorithmic analysis almost never tells you the ...
adrianN's user avatar
  • 5,931
3 votes
Accepted

What is `wasted space` parameter and why is it O(n) for a linked list

Different people seem to define "wasted space" in different ways. Some authors define it as any space in a data structure that's not used to store actual data; others define it as space that could be ...
David Richerby's user avatar
3 votes

How to find middle element of linked list in one pass?

Create a structure with a pointer capable of pointing to nodes of linked list and with an integer variable which keeps count of the number of nodes in the list. ...
Prateek's user avatar
  • 476
3 votes

Using B-method, and formal methods in general, to model and verify a reverse linked list

There are many approaches for verifying linked structures---arguably, more suitable than the B method---that you might want to use, depending on the language and properties you want to verify. Most of ...
ivcha's user avatar
  • 540
3 votes

What is the time complexity of enqueue and dequeue of a queue implemented with a singly linked list?

The comment in the book apparently assumes that your linked list implementation maintains two pointers, head that points to the first node in the list, and ...
Barmar's user avatar
  • 443
3 votes

The origin of list data structure

The first use of linked lists in their modern form seems to have been by Peter Luhn in 1953, when he implemented a chaining-based hash table on the IBM 701 machine. Linked lists are often ...
William Kuszmaul's user avatar
3 votes
Accepted

Time complexity of insertion in linked list

The question only says that the target list needs to be maintained in sorted order. It doesn't say anything about any other data structure that you may choose to use. The proposed solution first does ...
Gilles 'SO- stop being evil''s user avatar
3 votes

Algorithm to Compute High Water Mark

You can use a disjoint sets data structure to quickly solve your problem (exercise). This can be further improved by exploiting the particular nature of your problem. We maintain a list of intervals $[...
Yuval Filmus's user avatar
3 votes
Accepted

Are linked lists homogenious or heterogenious containers?

You say "linked list" without mentioning a computer language. First, a "Node" is not a linked list. It is a helper struct that may be useful to create a linked list, but it is just ...
gnasher729's user avatar
  • 28.3k

Only top scored, non community-wiki answers of a minimum length are eligible