Triple Ref Pointers - Computerphile
HTML-код
- Опубликовано: 21 окт 2024
- The 'magic' trick of pointers to pointers - Professor Brailsford explains how what might seem complicated will actually simplify your code. (See Extra Bits video for a code walkthrough)
The Professor's Code: bit.ly/Computer...
EXTRA BITS - Triple Ref Code: • EXTRA BITS: The Triple...
n.b. Message from the Prof: Many thanks to all of you who have pointed out that I got over excited at the end of this video and (on the LEGO model) did the pointer reassignment in the wrong order. The correct way ( in the model once again) was to do the short pointer first and the longer pointer second - which I think is done correctly in the downloadable C program.
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscom...
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com
Many thanks to all of you who have pointed out that I got over excited at the end of this video and (on the LEGO model) did the pointer reassignment in the wrong order. The correct way ( in the model once again) was to do the short pointer first and the longer pointer second - which I think is done correctly in the downloadable C program.
ProfDaveB your videos are awesome!
i love listening to you, even when am not getting anything
I guess it was the fun of having a long lego pointer that got you off track :p. Very nice videos that also is nice not just for beginners, but also people who have been programming for a while.
I watch these videos because of how excited you are! Your excitement shows through and makes them both entertaining and informative. If the cost of that is the occasional minor inaccuracy I'll take it.
"All problems in computer science can be solved by another level of indirection except for the problem of too many layers of indirection." - Fundamental Theorem of Software Engineering
I have been using C for the last 3 years and never understood the pointer to pointer concept. In fact, I was always afraid of it. After watching Linus Torvalds's TED talk, I was still very confused. Thank you Dave, for making me comfortable with triple reference. This has been the best explanation. Period.
Definetly relateable. I don't use pointers, except there is a reason.
And suddenly I understand pointers at a whole new depth. I understood them from a technical standpoint, but this here actually helped me understand some of the subtleties that make pointers so powerful a tool. Thank you!
Very nice. I'm old enough to have grown up with Algol68 too, where I was taught this. I've occasionally used it as well, even in C++ (where using singly linked list is somewhat out of fashion, shame). The video forget to explain the "triple" in the title, so let me add that. In Algol68, the essence of a reference is the ability to modify what is referred to, which implies that pointers are references, but also that having a simple modifiable variable, say of type int or real, already involves a level of reference (the variable itself has mode REF INT when its value has mode INT). Then the variable 'tracer' that holds a pointer to pointer to NODE has mode REF REF REF NODE (while at each instant the pointer-to-pointer value it holds has mode REF REF NODE).
6:00 - "And look! Look what you can then do, is you start with Tracer, you jump to that box, but then, you jump down the fireman's hose and you can take a look and you see that the next thing is chips. And you say WOWWWW! I've just seen beer! I'm looking ahead by this sneaky technique and I see chips, that's where I belong! I want the burger thing in there!"
Somebody please please please make an animation for this voiceover PLEASE!
hahaha
Yes
I must say, this video was..... on point.
For those asking why not just use doubly linked lists -- imagine programming in the early 70's. You could likely be creating software for machines that have less than 1MiB of RAM! If you wanted to manipulate or process large lists, where the size of a pointer on a 16-bit computer could be 2 or 4 bytes each, it would be very important to conserve space in memory by restricting yourself to singly linked lists -- which is how this pointer technique would come in handy.
Of course, now we have the luxury of computers that come with many GB of RAM, and high level languages that abstract away things like pointers, so the usefulness of a technique like this can be hard to understand right away.
I want nothing to do with a language that doesn't allow pointers. Extra GB of RAM or faster CPU is no excuse for inefficient code.
+Dave Smith That's a problematic stance. Pre-optimization is a common pitfall. Also, it's much easier to speed up clean code, than to clean up unreadable "efficient" code. You have to allocate your time and effort, and optimizing all code is a poor decision. Instead, you optimize the bottlenecks that you observe after writing the code, or areas where there is increased user demand. When you encounter an issue, you let the backpressure of that problem dictate where to optimize. Otherwise you end up creating more problems and much harder to maintain code.
Pointers are also not necessary for most optimization needs.
Linked list aren't memory efficient to begin with.
Retropaganda - Every form of data structure starts internally with a linked list. The links may be abstracted so the coder doesn't have to deal so much with maintaining the link, but they're still there. The only alternative is the much more primitive "unlinked list" - also called an array. Arrays are much less efficient at organizing data - it's more expensive to move all the data than just change a link - and is more error prone. Moden languages hide the details of how the data are linked, or present it as a structure that is more relevant to the information represented, but those links are still there.
@@retropaganda8442 of course they aren't, but is there a better approach?
Surely the way you explained this, there is no real difference between using a pointer to a pointer to the object (which can point to any blue box) than using a pointer to the object containing the next pointer? You can still follow the hoses to the next item in both cases. I think the *real* key point (excuse the pun!) that has been missed in this video is that a "pointer to a pointer" can point to the address of the *start pointer* and correctly insert an element at position 0 without treating it as a special case (because you can update the "start pointer" in just the same way as you can update any of the "next pointers" of the preceding element. This should have been made much more apparent as many will have missed that subtle point (again, sorry no pun intended). Shame because it was otherwise a great explanation.
This allows you to use one pointer with what is actually called multiple indirection instead of two pointers. So it saves some memory. Today this memory savings is not significant, generally. But in specific applications, such as embedded controllers, it can be very valuable.
Does it also help at the end? Looking whether a pointer is null would be save vs trying to follow a null pointer?
he made that POINT in the first video , this is a follow up video
watch the unlisted vid in the dscription.
As a CS student I must admit that I lauged at "well, by the principle of colored lego type theory ..."
I don't think I've ever heard somebody get so excited about pointers before and it's awesome.
love the lego demonstrations. but i did find myself struggling to think of where a solution like this has advantages over alternatives (double linked lists, tree structures, arrays)
One of the main advantages that appear to have forgotten to be mentioned is that inserting at the front is no longer a special case.
If you only use pointers to things, you have to check if you are inserting at the front of the list to modify your "start" pointer.
However, if you use a double pointer, you can point it at the start pointer and say "insert this". If it happens to be at the front, it will just replace the start pointer like it was any other pointer.
And to all those people saying you can just use normal pointers: Yes, you could. Using a double pointer results in much simpler code, though and arguably describes more closely what was intended.
Exactly! Well said.
This is actually used in the Linux kernel for lists.
Fascinating! People who delve into Operating System code have to be *totally* happy about pointers ...
Technically, last two steps should have been done in revers order.
We need to first make burger's next pointer point to chips, and then make the dereferenced tracer (aka beer's next pointer) point to burger.
But it's a cool technique if there ever was one.
7:19: "Do the long one first" If you do that, don't you lose all reference to "Chips" and would no longer be able to know what "Burger" should point at? Afaik, the pointer from Burger to Chips should always be constructed first, shouldn't it?
You need to remember it somwhere before changing it, yes, but it can be in some temporary pointer. In an efficient code, you would indeed do it your way.
Yes, he should have done it the other way around first to avoid the need of a temporary pointer.
burger.next = *tracer; // Set the next reference of burger to point at chips
*tracer = &burger; // set the next reference of beer to point at burger
burger.next = *tracer.next
@slavkosster Tracer is a pointer to the pointer of beer.next. So it should be burger.next = *tracer;
He says it here: 4:46
yes, sorry, of course :D I always got confused with pointers and I haven't coded with pointers in years.
My favourite technique for this kind of insertion is to just always work with node->next. To avoid having special cases for the first node, I simply make a dummy node as a local variable that points to the first node, and start the iteration from there. At the end of the loop just assinging head = dummy.next; is sufficient to handle insertion at the head of the list without special cases.
so you are basically making the head node second in the list.
Excellent explanation - very clear and concise. Using the lego blocks to visually show how it works was brilliant (even though pointer reassignment was in the wrong order)!
I know the downloadable sample code provided is just for learning purposes, but I'd just like to point out that in function PrintList(), there's no need for the "head" parameter to be a pointer-to-pointer-of-THING, as PrintList() will not be modifying anything (it just traverses the linked list and prints out "item" from each THING node). In my humble opinion, you could simplify things in this case by using pass-by-value for the "head" parameter instead:
void PrintList(const THING *head)
{
const THING *tracer = head;
while (tracer) {
printf("%s
",tracer->item);
tracer = tracer->next;
}
}
This would then be called from within main() like so:
PrintList(start);
NOTE: I've made the "head" parameter and "tracer" constants. This will prevent things like:
tracer->next = NULL; // item);
tracer = tracer->next;
}
}
Yes I agree that tripleref is somewhat overkill for 'printlist' On the other hand tripleref does make the RemoveThing routine rather more elegant than doing it the "traditional" way.
That's pretty freaking cool and powerful. As a programmer who codes in higher level languages, it's super interesting knowing this lower level stuff :D
I've gotta jump into C, it's brilliant!
Also, naming it a TRIPLE reference pointer where you have the pointer then the "double" pointer to pointer, it's a triple. Nice one programmers. Just pushing the "arrays start at zero" agenda :D
This is probably the best illustration of a linked list I've ever seen.
cheers love, the pointerpointer is here!
I was looking for this comment.
Lawa9919 I knew it!
Heh, it's a pointer that uses multiple indirection: en.wikipedia.org/wiki/Pointer_(computer_programming)#Multiple_indirection
So let me get this right. First, we use Tracer. Then we blink forward to see if we've gone too far and, if we have, then we rewind to where we just were. Seems simple enough.
Hahahah. If I might add a correction, you blink forward twice to check, then rewind, blink forward once, and change your direction.
Alex Blandin the problem lies in blinking forward, but then not being able to rewind. This leads to many fatal errors.
It's more like doing measuring a rock with a laser without the need to touch the rock physically in the first step. In other words, your robot doesn't have to move in the first step.
I think Ada 2012 can do triple ref. The pointer equivalent in Ada is the Access. Accesses are safer than C pointers since they are strong typed and casting is prohibited by default. When casting is absolutely necessary you can use the "Unchecked_ Conversion" package, but should be used with the utmost care. Great channel and vids, keep it up!
Thanks for this. I forgot to mention ADA. But I think you're right: ADA can almost certainly do it.
If you follow the link to EXTRA BITS, in the Info block of this video, you'll find that I've posted a comment there explaining why the 'triple ref' naming of this trick made a lot of sense in the Algol68 version, which was where I encountered it in the early 70s. There's also more details about the downloadable C version of the code.
The "triple ref" name is perfectly understandable and fine as a piece of history. But it's important to use the currently accepted name for this, too. Otherwise it somewhat inhibits the learning process. This language feature is called "multiple indirection."
Damn, I really love the way how this guys explains
These videos are tremendously interesting and helpful !!! Thank you so much ... !
I love the NULL lego ;)
Thou shalt not follow the NULL pointer, for chaos and madness await thee at its end.
Oh gosh, how did I miss that, lol, awesome!
Maciej Kadłubowski Falcon! In a few day
Isn't it a VOID lego?
The last blue lego in the chain is a pointer to the same type as all the others. ("void" is a type; "null" is a value.)
Explaining pointers with Lego. Well done, professor. It made clear why you would use pointers to pointers, something I didn't get with that introductory programming (C/C++) course which I got. It is about making it easier to implement a link in the chain. Next time vegetarian please given whole that biomass pyramid and world hunger problem. ;)
I can't believe that this channel about software gets so many subscribers. What percentage of the people can program at least a little bit? 10%? The internet never seizes to amaze, does it?
I have absolutely no idea what they are getting on about, but I do enjoy watching anyway.
Do we really need a separate variable for this? If we have a pointer *cur pointing to a node, can't we simply look at cur->next->data, instead of having a pointer *tracer that happens to point to cur->next?
Maybe I'm missing the point here, no pun intended.
Yes we can and we are. 8) This "tripple" pointer thing is bs.
What do you mean? Can you post the equivalent code for your approach, please?
On my phone, so pseudocode:
thing *cur;
thing *ours = [the value to insert]
cur = head;
while (cur != NULL) {
if (cur->next == NULL || cur->next->data > ours->data) {
ours->next = cur->next;
cur->next = ours;
break;
}
}
@Benjamin, there are a few issues with your (pseudo)code:
1. You've got no code to actually traverse the list; you could add `cur = cur->next;` after the `if` statement.
2. Your code will fail to add any node (i.e., THING) at the front of the list. Think about what happens when I pass an empty list to your function. The `while` loop test will fail and your function simply exits. You can fix this issue by adding the following two lines after the `while` block:
newp->next = head;
head = newp;
3. Even after fixing those two issues described above, you run into the biggest problem of them all. Any changes you make to `cur` inside this routine will not get reflected in the caller (i.e., calling function). This is because `cur` is local to your routine and gets "destroyed" when it stops executing. Remember that `head` in this case receives a copy of `start` and not `start` itself. This is called "passing by value". If you suspect that the head of the list might change, it's better to pass a pointer to the head pointer rather than the head pointer itself, which is what Prof. Brailsford has done. This is called "passing by reference". This is a standard technique in C -- if you want to change a value of interest, pass a pointer to it.
With your approach, no matter how much you modify `cur` and `head` inside the routine, the variable `start` does not get affected.
The first two are easy to explain: I'm currently evacuating because of Hurricane Irma, so I'm on my phone. Also, when I wrote my comment I had been up about 24 hours.
As far as your last point goes: the professor appears to be using the "dummy head" technique. That is, the first node is a proper node, but it has no data. This means pointers to the head of the list never have to change.
Yes, cur is a local pointer, but that's okay because it's just used to scan the list. cur disappears, but cur's referent doesn't.
Nice pointer they used the curve mantis to catch the S while the skinny mantis could make a different stand to confuse the pointers
This is such a cool video series.
Drinking game: take a shot every time prof dave says pointer
Nice explanation! I had a problem to solve one time that required at times a *****char[] to point to my data. It drove my (1988 Microsoft C) compiler (and me) crazy trying to figure out how to write it so the compiler stopped gagging!
Oh, references to pointers have been so useful for me!
Do a tree data structure! This made so much more sense thank you guys
Any design problem can be solved by adding another layer of indirection - except for too many layers of indirection.
I learned this technique from browsing through XWindows server code around the early-mid 90s. I didn't know what, or if, there was any real name for it, so in my code I referred to it as pnp (Previous 'Next Pointer'). Technically it may have been more accurate to name it ppnp (Pointer to Previous Next Pointer), but that was a little too wordy.
Why not just pointer to previous next? Or in short ppn.
Double linked lists are the way to go nowdays, those allow for facilitated traversal with only 8 bytes more, but if you dislike wasting memory, you can implement it with a xored pointer system. It may be interresting to present those
The way to go nowadays is the same as it ever was and to use the most efficient data structures and algorithms to match the required use case, anything else is lazy and the reason many applications are way slower than they need to be.
"Oh, I'll just throw an extra 8 byte pointer in each list node", at least to me is a very bad attitude to spread. That 8 bytes may not seem like much, but it has huge downstream effects on busting your very limited space cache hierarchy; and the way you should think about "reaching out" to main memory is to avoid it like the plague.
When in doubt, consider main memory as the new "Hard Drive" and SSD as the new "Cassette Tape"
Sorry for the rant, but I downloaded a PDF reader the other day that was 640MB in size! A PDF READER! So yeah, excuse me if I'm a bit touchy on the topic.
Xor'd pointers otoh is a very neat trick!
So how about doubly linked-lists? Where one pointer points to the next object, but another points to the prev object.
They are a possibility but they take additional space for the second pointer
With double linked list, you have a link looking backwards as it is, this technique isn't needed . The reason we need this technique is precisely because we don't have a look back pointer!
To clarify, in a singly linked list, you only need to use an extra pointer when you're inserting something into the list, which temporarily uses a negligible amount of extra memory, but in a doubly linked list, every single item in the list gets another pointer, which increases the overhead of the structure. This is probably negligible in the majority of cases, sure, but it's a drawback for sure.
You have two single pointers in that case. They are not pointers to pointers. Each of the pointers in a doubly linked list points to either the next object, or the previous object.
A pointer to a pointer is something that points to another pointer. So you're getting the address of another pointer, which in turn points to a variable or object of some sort.
It's technically called multiple indirection: en.wikipedia.org/wiki/Pointer_(computer_programming)#Multiple_indirection
i am learning a lot, thanks prof
You can also use an extra node at the end of the list that you use as a terminal node with no payload (a caboose). Then when adding a new node that should go before the node you are pointing at, you insert it after the exchange payload. And Voila! It's faster but you need an extra node for each list.
Yes, in theory. With care this can be done without an extra node (essentially special case code for end of list.
This doesn't work for any use case where the node address is used elsewhere or if it's expensive or impractical to "relocate" the data field (intrinsic lists for instance).
Ha, I used the Malvern Algol 68 compiler on Multics machines when doing my first degree in 1980-4. Happy days. I loved Algol68 at the time.
I was able to come up with a recursive approach to reserve a linked list using triple ref pointers.
void reverse(Node** head) {
if (*head && (*head)->next) {
Node* rest = (*head)->next;
reverse(&rest);
(*head)->next->next = *head;
(*head)->next = NULL;
*head = rest;
}
}
But it's not much different than using simple pointers:
Node* rev(Node* head) {
if (!head || !head->next) return head;
Node* rest = rev(head->next);
head->next->next = head;
head->next = NULL;
return rest;
}
head = reverse(&head);
so if you wanted to go up multiple levels would you need a dedicated link to the start?
For example a CString Array made out of pointers to pointers because strings in c are char* and an array of strings are char* variable_name[] or char**.
I was looking for something referencing that. Or maybe dereferencing? ;)
I'll see myself out.
It seems that you also have the added benefit of always having the start address as well and leaving that unaltered.
Good to see Donald Knuth's Art of Computer Programming on the bookshelf!
Wonderful explanation.
So is the power the ability to look two steps ahead while retaining the point of reference?
Just to note, this technique has less concern with "keeping half a finger on previous," because the same technique of "peaking at the next in the list" is compiled in EXACTLY the same way as a double pointer mechanic. It literally boils down to typecasting to help the programmer, but meaningless at the assembly level.
I've never come across a need to create a double pointer except with dynamic 2D arrays.....and that's pushing it.
It's maybe already been mentioned but I remember programming the Mac 68000 or perhaps a G3 series in C and there were pointers to pointers used for various OS calls or memory allocation which according to the Mac programming book I used were called "handles". Is the Mac alone in calling pointers to pointers handles?
A handle is, more generally, a value which represents some specific "thing", but you aren't intended to do anything other than use it to name that specifc "thing" when requesting further operations involving said "thing". A handle might be a pointer (typically to an object you don't know the structure of), but it could be an array index (the unix 'open' returns a file 'handle', which is almost always an index into a table of open files), or some kind of hash/secret key.
I'm a simple man. I see LEGO I click.
fuckwad wow, so insightful of you. and your sense of humor, outstanding. you should definitely listen to your own advice written on your profile image.
Don't take trolls personally, it's just dry humor
Love the video, and I'm totally being unnecessarily critical here, but I think it would make more sense within your Lego analogy to have the existing black pointer of "beer" point to "burgers", and then have the yellow pointer of "burgers" point to "chips", rather than making the existing pointer that used to go from "beer" to "chips" now begin at "burgers" instead.
Ivar Kråbøl i can see where why you think that. but if you see the black part going from "beer" to chips as a value pointing chips, then it is correct that it now belongs to "burgers". because "burgers" is now pointing to "chips". the yellow part is a new pointer value. i think you would have been correct if he took the blue block from "beer" and used it as the blue block for the new "burgers" thing
This expanation is probably a bit confusing for new programmers (as pointers usually are). In essence what he is saying is that because a pointer can dereference to a value, a double (he called it triple) pointer can dereference to addresses (and go do so twice). This means the first dereference will give you the address of the 'burger' and the second dereference will give you the address of chips. And you can cast (*) on either address given to get it's value.
A good example of pointers to pointers that is most commonly used is a string of text. You are pointing to a list of pointers that each point to a single character.
Neil Roy no. in C, a string is just a pointer to a character. the characters are stored next to each other in memory (they are an array). to get a pointer to the next character you can increment the pointer to the character using:
p++;
or you could cast it into an array and use an index on this array, to get the character you want:
c = arr[i]
because arrays in C are basically pointers
Haha, I don't know if you were joking, but a string like that would be really funny. It would take O(1) time to change all the E's to I's, and O's to U's, how marvelous!
Think about how efficient substitution cyphers would be!
the two pointer method is more efficient, though, because you don't have to deference memory twice for each item - you just shuffle your prev/next points around which can be done with register renaming without a stall.
Every optimizing compiler will turn the double indirection method into optimal register stores, so nothing is lost. However, if your platform happens to be register constrained this method is likely to still generate optimal instructions (particularly for platforms with fast double indirection instructions).
I didn't know this was called a triple ref pointer. But seeing something like p->next->next in C linked list code is pretty common.
So, here's my question: this video mentions the "triple ref" technique, but there's only two dereferences. The number of references should match the number of dereferences; so where is the third dereference coming from that gives this technique its name? FWIW, I've only known this method as the "double dereference" method.
foo->bar->quux = x
What's the point?
Is it for ease of use, code readability, faster, smaller?
There are different types of coders and each type will answer differently. Some will approve because this eliminated extra conditional checks (so, faster & smaller), others will disapprove because this requires an additional layer of abstraction (conceptual complexity is higher). I would say if you can't get your head around this level of abstraction, maybe computer science isn't for you.
I can get my head around that level of abstraction among the other ways of doing things and that's why I asked the question.
sorry, looking back at what I wrote I sound more confrontational that I intended. What I was trying to say was that this is a level of abstraction I'd expect of any competent C coder. If it were above the level of conceptual complexity of the average coder that would be a reason to avoid it.
For the other non-programmers puzzled by the term 'dereference' it simply means we're going to follow this 'pointer to a pointer' (the lego chain) and STOP. We're not going to follow down the link of the pointer we've arrived at (the black lego hose), we're going to look at the pointer itself. In this example, that's how we know we're at a thing with the value "beer". If we were to follow the pointer we arrive at a thing with the value "chips".
Absolutely brilliant !
Whats the advantage of this implementation versus just using two iterators, one pointing to the the nth element and one pointing to the n+1th element?
On a 16 bit machine, it saves two bytes of RAM. And you can update the start pointer when inserting an element at the front of the list.
How is it different from say keeping a backup of the start pointer so you don't lose where the list starts as you traverse down the list to or remove things?
This is the Linus Torvalds trick, if I recollect correctly. He said that you don't understand pointers if you haven't got an intuitive grasp of this. (Edit: The difference here is that Linus spoke about the removing case wherease Prof. Brailsford talks about the adding case. Pointer to a pointer nevertheless!)
Word has it Professor Brailsford drove around to 5 shopping centres to find that Lego chain piece just for this video.
Sean's two boys kindly loaned various hoses and chains from their own collection of LEGO. I should also add that no expense was spared for this video. Even with the loaned hoses I didn't have nearly enough, so I had to order a dozen more from (the UK instance of) LEGO's "buy a brick" service. Cost me £25. Bankruptcy beckons !
lol
Wow. The person who filmed this at 8:13 was my teacher in secondary school
Love how I just got assigned to program a list.
Kind of interesting that this video is less than half the length of the previous one... Like he says, it looks like it would complicate things, but simplifies them...
I wish my math teacher was like him. I'd have been so much more into science!
in the case of inserting at the head of a linked list, either I'm missing the point or this is unnecessarily complicated!
what's wrong with pointing 'start' to the new THING, and point the new THING to the previous head of the linked list?
only two pointers update
Without the additional indirection, inserting an object at the head of the list would require completely different code than inserting it in the middle. More importantly it couldn't be done by a subroutine call without passing a pointer to 'start' in case the start has to change.
so what's the difference between this and a linked list ?
You could do it perfectly fine without a double pointer. Just compare your new data to p->data and p->next->data. What's the problem with that? Way simpler than the other syntax, which I couldn't be arsed to write.
SwordQuake2 I haven't thought it through completely but I'm not sure that would handle all of the edge cases as gracefully.
The edge cases are what if p->next is null, you have to check for that before. You also have to think about adding to a list that is empty - ie adding the first item, does it work for that?
Thanks again Julian for acting as my spokesperson while I was on vacation (!)
SwordQuake2 That wouldn't work for inserting an object before the head of the list.
I believe that programmers not knowing this technique for inserting an element in a linked list is one of Linus Torvalds' pet peeves.
I dunno man, this metaphor seems to be breaking down. If I could custom build some legos, I'd build hoses that you could attach other hoses onto.
Also, the hoses should be directed. I really noticed when you "flipped a pointer around", which is just not an operation you can do to a pointer. And now I don't see why you need a double pointer. Why not (pseudocode b/c I can't be bothered to run it through a compiler):
struct list {
item : thing
next : *thing
}
void insert(list* list, thing* burger) {
while (list->next != null && burger->item < list->next.item)
list = list->next
item->next = list->next
list->next = item
}
I mean, I guess there are two pointers in here (one for the list, and then another inside the list), but it's still really unclear how this is a _triple_ ref technique.
it's the same...
void insert(next** list, thing* burger) {
while (*list != null && burger->item < (*list)->item)
list = &((*list)->next)
burger->next = (*list)
(*list) = burger
}
Why not just use an empty thing as the head and one pointer to check the next thing item?
Can you do something comparing standard link lists with the kind that Haskell uses where it's basically backwards?
Not clear to me what you are asking. Though Haskell certainly uses pointers internally, the user does not get to see or manipulate them, so I cannot see how anything like this would apply there. Besides, this kind of insertion by pointer manipulation is inherently imperative, so would not apply in Haskell. In Haskell if you insert something in the middle of a list, the whole beginning of the list is copied to new nodes, only the unchanged tail can be shared with the original list.
Joshua Hillerup i think they are exactly the same. it's more convenient to insert something into the front of a singly-linked list than into the back, because inserting into the back would require going through the whole list. so people tend to keep these lists reversed as long as possible so they can insert things into the front efficiently. that's why you see a lot of reversed lists. usually people reverse the list when they are done, to give it the correct order again. the exact same problem exists with the singly-linked lists in this video
I feel like it's explained really badly whats going on and why it's happening. I'm programming c++ and I'm quite new to it, so maybe I missing something, but I don't really see what is the deal with this p** technique instead of just having a pointer to prev element while you iterate thru list.
Dmitry Shap I also found it quite hard to see at first, but given a long list most of the computation will be in traversing the list. With two pointers you'd have to update them both, while with the one pointer you'd only have to do "p = &(*p)->next_item;" which is faster.
the speed is negligeable by today standards
Pointer to previous element does not work when you need to add before head because there is no previous element, only a pointer
+Just AGuy - "Today standards" ?? You mean taking longer time with a 10000 time more powerful machine ? That's YOUR standards ??? You do what you want, but there's NO today standards... There are "objective" standards according to your industry, "today standards" still requires performance on embedded AND AAA-kind of games...
If you think yourself as a "hacker" because you do CSS, sorry to tell you that YOUR todays standards suxxx...
Lol, you placed your ridiculous hacker CSS joke based on nothing, happy? Can we have an adult discussion now?
Most programs today does not require this kind of optimization. Yes some does, but no, not the majority. That is what I mean by today standards.
Still, it''s simpler to do it without that tracer-triple reference pointer, because a linked-list is a tracer-n reference pointer from itself. (where n equals listlength)
[edit]
So when you loop from the start-pointer:
if current pointer's object-name 'burger'
insert the flippin burger (set burger-object.next-reference to current.next, and set current-object.next-reference to the burger)
else set the currents pointer to the current pointer's next object, and continue the comparing of names
ps Hooray for overly complex explanation :D
Pointers are great!
This video is making me hungry
What about some concurrency mental gymnastic with LEGO for the next episode?
A little mistake in the video but not in the C code...
In the video the long fire hose from "BEER" was connected to "BURGER" before the short fire hose from "BURGER" was connected to "CHIPS".
If performed in that order then we would have lost "CHIPS" after disconnecting it from "BEER", because nothing would then point to it, and so we would then have no way to tell "BURGER" how to point to "CHIPS".
The correct order is that the short fire hose should have been used to connect "BURGER" to "CHIPS" before using the long fire hose to connect "BEER" to "BURGER", this means that immediately before connecting the long fire hose from "BEER" to "BURGER" both "BEER" and "BURGER" point to "CHIPS" until the "BEER" pointer is changed to point to "BURGER" instead of "CHIPS".
Maybe it would have been more clear if the pointer was represented as a combination of the blue block and a fire hose always connected to it, but not necessarily connected to a grey piece because the fire hose alone does not represent the pointer; the fire hose merely represents the value of the pointer.
The C code does have the steps in the correct order though.
It seems like a little thing but it makes all the difference and I thought I should mention it just in case it helps anyone else who might be trying to learn about pointers and was confused, particularly because @7.17 Professor Brailsford says "let's get this right" but he unfortunately then proceeded to get it backwards.
Thanks for the videos, I've been programming for ~30 years and still enjoy these just for fun!
Very nice, but there is a mistake in the end. You have to set the link from burger to chips *before* you change the link from beer... otherwise you lose any link to the "chips" structure.
Sorry, but I don't understand why you couldn't use a simple variable to hold the address of "where you came from", and update it as you traverse along the list.
The title ‘Triple Ref Pointers’ is misleading. While it is true that, since the variable ‘tracer’ is of type THING**, the memory location of this variable is THING***, that memory location is never used (or needed) as a value in the program. Moreover, the variable ‘tracer’ itself is superfluous. It's initial content is but a copy of the content of the variable ‘head’, and the latter then remains unused. Therefore, one can remove ‘tracer’ and simply use ‘head’ instead. The parameter ‘head’ itself is just a local variable and indeed can be used as any other such variable.
Nice explanation of the insertion into linked lists. Maybe the next interesting thing to show would be vectors, when I look at this lesson of Bjarne Stroustrup: ruclips.net/video/YQs6IC-vgmo/видео.htmlm29s
In essence he says that a) the linear search is bad, and what's making it so bad is the fragmentation and the rising probabilities of cache misses. On the other side, caches get bigger. As the series started with associative arrays, we already know linked lists are kept short typically anyway.
To a developer rather used to 4th generation languages in my profession (I started in 6502 assembler, 68000 assembler and then also C as a hobbyist, yes, but never had to do serious assembler or C/c++ development) it is a bit of an odd discussion about the speed of access to memory organized in different ways. As a database developer, I'm also profiting of larger and larger caches and caching done even to the file level and in memory held data is a topic for sure, but it really seems like a luxurious problem of even faster RAM access with structures sorted in memory.
I know what a pointer of a pointer is and I've been programming for 34 years but I really don't understand him.. I'm quite confident that he is indeed intelligent but the way that he describes the procedural style is not registering.
maybe i am overlooking something, but the entire video could have been condensed into 10 seconds
can't you just do two p's? one to reference the current pointer and one to hold the previous pointer?
but... pointer to a pointer... SHOULD (in my opinion) be the same as one level pointer. it's still just a variable which value is a memory address. that's, in my mind, a type. pointer is a type, regardless of what it points to.
and yes, as I was writing that, I started realizing issues with that approach, but I am still of the opinion that it should be as I wrote, and those issues are worth solving to keep the concept straightforward.
In C pointers reference actual bytes in the memory. It's all 0s and 1s. A pointer not only stores the location but also the way to interpret the 0s and 1s at that location (except void*). A pointer can't be at the same level as a pointer to a pointer because the bytes need to be interpreted differently. That's why you can't put char* and char** as the same type.
Cool data structure lesson :-D
Love this guy
Clear as mud. Can't you just explain in terms of bytes?
How is this easier than keeping the previous location in a temp variable?
let me know if you find the answer
Insert to the front, into an empty list, or at the end are all coded the same, no 'buffer'/previous to be kept, and once written cleanly, is normally trouble free for edge cases.
I guess I'm too much of an assembly guy... I still see the temp register as the easier way of doing it.
Define "easier". I find this easier because I've done it numerous times. There are no "extra" corner cases (insert at front/end) and this turns into optimal instructions under even the simplest optimizing compilers. Also, this code requires fewer test cases to achieve total code coverage. This does have what I'd describe as higher conceptual complexity, so no, it isn't easier under all definitions.
You placed the WINE item just a little bit off, so it'll drive people with OCD insane, didn't you?
Nice alternative to a doubly linked list
Or just keep two pointers, *next and *previous, while iterating.........
+diamondsmasher
That's exactly what I was thinking.
The problem with the *prev pointer is that it doesn't work with the first item in the list, that you have to treat separately. The beauty of the technique presented here is that there is no special case. No "if (p == head)" needed. Might seem trivial but it's actually a big advantage. For example if you're going to create a function that works on the list, then the function doesn't need to know where the list starts, and you can indifferently pass the whole list to it, or any element within the list.
with a double linked list, you don't have a head unless it is a cyclic one. The only reason for a head pointer to exist is because you can't go backward in the list. So you don't check if p == head but if p->prev == null.
The main advantage of double linked list is that you don't risk to loose the head with the associated memory leak and it is easier to use for some because of there is no head.
Actually, double linked lists have head (and tail) as well unless they are a cyclic one. Head is defined as the item with prev == NULL, tail with next == NULL. In a cyclic list, there is no head or tail, you just remember where you started.
very interesting code. i didn't understand how intuitive it was until i saw it. but it has some issues
Never fear. The cavalries are here.
It would be faster, less error prone and use less storage to modify the connections the other way around: set burger to point at chips first, then redirect the pointer from beer to point at chips instead.