86
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 travelled by fastPointer before meeting $=(x + y + z) + y = x + 2y + z$
Since fastPointer travels with double the speed of slowPointer, and time is constant for both when both pointers reach the ...
47
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 plausible due to the way it is sketched).
What you really want to prove is (using the same variables as described in the diagram in the accepted answer above):
$z ...
24
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 over the list, one with double speed. When the fast one reaches the end, the other one is half-way.
17
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 that head != null and tail != null):
function enqueue(value) {
node = new Node(value) // O(1)
tail.next = node // O(1)
tail = node ...
7
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 element
for example.
Of course, one might say that you can always ignore the second link,
but in that case, it is no longer doubly linked, but only an unused
...
7
This is known as the "order maintenance" problem. There is a relatively simple solution using $O(1)$ amortized time for both queries and inserts. Now, by "relatively simple", I mean that you have to understand some building blocks, but that once you get those, the rest isn't hard to see.
http://courses.csail.mit.edu/6.851/spring12/lectures/L08.html
The ...
7
Instead of simple numbering, you could spread the numbers out over a large (constant sized) range, such as integer minimum and maximums of a CPU integer. Then you can keep putting numbers "in between" by averaging the two surrounding numbers. If the numbers become too crowded (for example you end up with two adjacent integers and there is no ...
7
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 list, you just make the new list head the node you want to insert, and link it to the previous list head.
If you want to insert at the end of the list, you can ...
7
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.
A simple, almost silly solution, is just increment the middle node every two nodes
function middle(start) {
var middle = start
var nextnode = start
...
7
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, matrices are two dimensional and so concatenation may be meaningless if the sizes do not match up. That is to say, all rows need to have the same number of ...
6
One simple approach might be to use a doubly-linked list of extents, where each extent represents a sequence of contiguous records. The records within each extent could in turn be represented with a doubly linked list.
This preserves your ability to do $O(1)$ time splicing, and now the insert operation takes $O(k)$ time, where $k$ is the number of extents (...
6
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$.
Enqueue(val) is just Push(val).
For Dequeue():
ReadBegin().
Count the number of anything else - number of $d$ in the whole stack (which should be always non-negative). Push $y$ or pop $...
6
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.
merge(A, B) {
if ( A.size == 0 ) {
return B
}
if ( B.size == 0 ) {
return A
}
if ( A.head <= B.head ) {
return A.head + merge(A.tail, B)
}
else {
return B.head + merge(A,...
6
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 every level, then each node would have $\theta(\log n)$ pointers in it, since that is the expected height of a skip list with $n$ nodes. The total space used ...
6
Elaborating on Hendrik's answer
If it's a doubly linked list, iterate from both ends
function middle(start, end) {
do_advance_start = false;
while(start !== end && start && end) {
if (do_advance_start) {
start = start.next
}
else {
end = end.prev
}
do_advance_start = !do_advance_start
}
...
6
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, J. C. Shaw, and H. A. Simon began their investigations of heuristic problem-solving by machine.
5
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 are several ways to weaken you model to drop to equivalence with linear bound automata or lower.
Ginsburg, Greibach & Harrison [1] give a machine called a ...
5
The algorithm will always terminate. Look at the case where $n=2$. Initially we'll have 1->next = 2 and 2->next = 1. In the first iteration we'll change 1->next to 1->next->next = (1->next)->next = 2->next = 1 so 1->next will point to 1 and the loop termination condition applies, so we bail and return 1->data.
If $n>2$, ...
5
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 is worthwhile.
History of Lists
Let's start with the definition of a List, in Computer Science, as described by the developers of the structure (Newell, Shaw,...
4
You don't just store the values, you store them along with the keys. So when you search for a key in the linked list you traverse through the list and look for the key you want.
4
You can do it in $O(n)$ as follows.
1) Build an hash table by traversing the linked list and adding its elements to the hash table. In each iteration, search the hash table for the current element being considered in the iteration. If the element is not found, add to the hash table the element value as the key, and 1 as the corresponding value. If you ...
4
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 in a wait-free way. It's okay if consuming the items is not wait free, but producers absolutely must not block no matter what the other threads are doing.
...
4
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 is more expensive.
4
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.
Traversing over all elements will not change, you still check them all.
If you want to make concurent task, why bother with skip list?
Just make ten pointers from ...
4
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 next or something!
You are right that in a singly-linked list (one with a next pointer but no pre pointer) it is illogical and inefficient to add new items to the end of the list. Singly-linked ...
4
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 violates an invariant, while Java wants to avoid that in all cases. Java aims to raise exceptions when invariants are broken, or, when that can not be detected, ...
4
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 or two for the problem
3
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 not work" does not work because you do
not know the index of an element $S_i$ in $F$ organized as a tree.
This is what is addressed here. The problem is ...
3
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 provably requires $\Omega(n\log n)$ comparisons in the worst case.
3
Sort the linked list in $O(n \log n)$ time.
Go through each element of the list in their order and remove the element, if it is the same as the previous one in $O(n)$ time.
The total complexity is $O(n \log n)$, which is what you are searching for.
Only top voted, non community-wiki answers of a minimum length are eligible
