91
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 ...
51
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
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 ...
7
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.
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
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
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
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,...
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$, ...
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
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
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 the approaches rely on separation logic (which was in big part motivated for verification of linked structures).
Some tools include:
Full Functional ...
3
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.
struct LL{
struct node *ptr;
int count;
}start;
Now store the address of the first node of linked list in $start.ptr$ and initialize $start.count = 1$.
Ensure that the value of $...
3
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 complete story and never should be used to justify blanket statements like "this data structure is the best if you need operations x,y,z".
3
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 used to store data but isn't being so used at the moment.
So, in the first definition, a linked list has $O(n)$ wasted space because every entry of the list ...
3
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 last that points to the last node.
With this design, appending to the list is simply:
list.last.next = newNode;
list.last = newNode;
But removing the last node requires finding the 2nd to last node, so ...
Only top voted, non community-wiki answers of a minimum length are eligible