# Tag Info

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

You can refer to "Detecting start of a loop in singly linked list", here's an excerpt: Distance travelled by slowPointer before meeting $= x+y$ Distance ...
• 1,061

### 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 ...
• 651

### 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 ...
• 27.7k

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 ...

### 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 ...
• 315

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 ...
• 19.1k
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,...
• 600
Accepted

Other than saving space, the first advantage I can see for singly linked lists over doubly linked lists is to avoid having to update two links instead of one when you modify the list, when adding an ...
• 19.1k

### 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 ...

### 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. ...
• 247
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, ...
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 ...
• 3,235
Accepted

### If the list lengths are m and n, why does the merge take O(m+n) operations?

You are asking: Now what should be the order of merge and why? First of all, we need to fix the merging algorithm. I'll assume the canonical one, i.e. ...
• 71k
Accepted

### Is a stack machine with a forward read iterator Turing complete?

Your model is Turing-complete, unfortunately. You can simulate a queue in your data structure using the following algorithm. It introduced 3 new stack symbols: $d, x, y$. ...
• 478

### 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 ...
• 247

### 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 ...
• 4,371

### Is a stack machine with a forward read iterator Turing complete?

Your model is Turing complete (unlike what I previously thought), see user23013's answer a sketch of the proof (the essence is you can simulate a queue, and queue automata are Turing complete). There ...
• 17.7k
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 ...
• 14.6k

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 ...
• 4,133

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 ...

Yes. Singly linked lists are easier to work with in highly concurrent situations, because there's less data to keep consistent. For example, suppose you want to append a lot of items to a linked list ...
• 5,722

### 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 ...
• 4,696

### 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. ...
• 9,325
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 <...
• 1,044

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 ...
• 14.2k
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 ...
• 10.9k
Accepted

### Order-preserving update of a sublist of a list of mutable objects in sublinear time

At the time of writing I was not absolutely sure what the problem was. This lead to a more general second answer. See details in discussion at the end of this answer. Apparently, the "idea that does ...
• 19.1k
Accepted

### Sort doubly linked list efficiently

Mergesort keeps its $\Theta(n\log n)$ worst case on linked lists. Double-linking can't help (except perhaps by improving the constant, though it's hard to see how), because every comparison-based sort ...
• 6,519