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.

hahaha

Yes

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.

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?

Fascinating! People who delve into Operating System code have to be *totally* happy about pointers ...

Definetly relateable. I don't use pointers, except there is a reason.

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.

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

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

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.

Exactly! Well said.

so you are basically making the head node second in the list.

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.

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

Why not just pointer to previous next? Or in short ppn.

Thanks for this. I forgot to mention ADA. But I think you're right: ADA can almost certainly do it.

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.

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!

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

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

I was looking for something referencing that. Or maybe dereferencing? ;) I'll see myself out.

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

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.

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

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.

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!

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

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.

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

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

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.

foo->bar->quux = x

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.

Not quite - when inserting a new item before the first item in the list, you still need a pointer to the 'start'. The first item's 'previous' pointer won't point there, because it has to point to an object (in this case null, since there is nothing before it,) not to a pointer.

If you structure things such that your head looks just like any other node then you can make doubly-linked rings which have the head node before the first real node, and after the last node. In empty lists the head "node" points to itself. In this structure you can write insertion at any location without any extra boundary checks (on either end)

So, instead of simply holding a pointer to the head of the list, you would instead hold a pointer to a fake object which indirectly points to the head of the list. Then code which traverses the list needs to be modified to check for this fake object instead of a null pointer to know when they have reached the end. Workable, but I'd have to look at some actual code to see whether this approach is more or less advantageous.

Given: struct LLNode { LLNode *next; LLNode *prev; }; inline LLNode *LLNode_getNext(LLNode *node) { return node->next; } struct List { LLNode anchor; }; inline LLNode *List_begin(List *list) { return list->anchor.head; } inline LLNode *List_end(List *list) { return &(list->anchor); } #define List_INITIALIZER(me) {{&(me)->anchor,&(me)->anchor}} List myTypeList = List_INITIALIZER(&myTypeList); Use is: struct MyType { LLNode node; /* whatever else you want */ }; Assume: MyType *otherInst; //to be inserted Walking the list looks something like; LLNode *node = List_begin(&myTypeList); LLNode *end = List_end(&myTypeList); while(node != end) { MyType *myInst = container_of(node,MyType,node); if (MyType_leftBeforeRight(otherInst,myInst) ) break; node = LLNode_getNext(node); } LLNode_insertBefore(node,&otherInst->node);

That does not work for head though because there is no node pointing to it

He said next: so you can go to head and look at its next pointer.

The issue is that it won't allow you to add before head, e.g. if you would want to add “almonds”, because there is no item pointing to the head. You could of course make a special case for that but programmers hate special cases, they make everything harder to maintain.