I read it like 5 times and I don’t understand
In: 1
Objects in the list are not stored in memory sequentially.
As such, when you need to find the next item in the list, you need a pointer telling you where to go.
In a single link list these pointers are monodirectional. They point you toward the next item in the list and the last item often points you back to the first.
In a double link list the pointers are bidirectional. They point you toward the next item as well as the previous one.
This can make certain operations faster, but takes up more memory.
Single linked list: you can only traverse the list in one direction. Each node only knows where the next node “downstream” is…it doesn’t know where it’s upstream node is. You can only traverse it in one direction by following nodes downstream.
Double linked list: you can go in either direction, because each node knows *both* (“double”) the upstream and downstream nodes.
A singly-linked list lets you go forward only (item 0, item 1, item 2 … item n), whereas a doubly linked list lets you go forward or backward.
Mechanically speaking, a singly linked list is a bunch nodes where each node (at a minimum) has some kind of value, and a pointer to the next node, whereas the nodes in a doubly-linked list have that plus a pointer to their previous node.
So this
`{
Val: X,
Next: some_node
}`
versus
`{
Val: X,
Next: some_node,
Prev: other_node
}`
Imagine a warehouse filled with boxes, you open up tge first box, and it contain3s some stuff, and also the location of box 2. Box 2 has its stuff and the location of box 3, and so on. If you hit box 7, grab its contents, and realize you need box 2’s stuff again, the only real way to remember exactly where it was is to look in box one again. That’s a singly linked list. A doubly linked list would also have to location of the previous box in addition to the next one (ie the location of box 6 and 8 are inside box 7)
Latest Answers