Introduction - Memory Management is kind of a Big Deal
Controlled memory management is one of the most important features that C++ (and C) have that other other famous programming languages (like Java, C#, Python) don't have. Although the other languages often give you what you need to work with data, C++ allows for very fine-tuned control of data because of the use of pointers.
We'll define what pointers and references are, and go over all of the possible code examples you'd use them in. (It's especially important to know for function parameters, since it saves a LOT of time if you pass by pointer or reference.)
Note: This topic is a bit difficult for beginner programmers, and if you learn Java first, you'll never really even learn about pointers since the language doesn't use them (although Java does use references) Still, learning about it is worthwhile.
What Are Pointers and References?
To start out with, remember that in programming, our data (variables, objects, everything) lives in memory (RAM, specifically), and so each variable in our program has a specific address corresponding to it's specific location in memory.
A pointer is a C++ variable that stores the address of some other variable.
Note that pointer syntax is to declare a variable with an asterisk * next to it, accessing the address of a variable with with an ampersand &, and dereferencing a pointer (accessing whatever is inside the address of a pointer) is also with an asterisk *.
Think of a pointer like knowing a specific index in an array: if you know the direct index, you can just look directly to find the variable you want.
A reference is when two variables refer to the same data in memory. You'll know because references use the & sign.
In C++, references are very helpful in function calls, either to update an external variable value inside the function, or to make sure you don't need to copy a large data structure like a vector unnecessarily.
(Note: We're using lvalue references specifically. rvalue references are an advanced topic that we'll talk about in another tutorial. (If that doesn't make sense, don't worry.)) Pass By Copy To Function
Passing a copy of a variable does not change the original variable. When the function PassByCopy is called, a new variable named srcmake2 is created in memory, and the value of srcmake2 is set to whatever was in srcmake1's value was at the time.
Output: 10 5
Pass By Reference To Function
Passing a variable by reference means that the function's variable (srcmake2) is actually the same data in memory as the original. That means any changes to the referenced variable will affect the original (and any other function calls using that reference).
Output: 10 10
Note the only real difference is the & sign next to the function parameter, srcmake2, where we declare that we're passing the variable by reference. Pass By Pointer To Function
Passing a pointer to a function is really dumb, and you should only really do it if you're working with linked lists or trees.
Notice the three changes: 1) When we call the function, we need to pass the address of the variable, instead of the variable itself. 2) In the functions parameters, we have to use a * to indicate the variable is a pointer. 3) Whenever we actually want to use the variable in the function, we have to reference it.
Output: 10 10
Pass by reference if you can. Passing by pointers (for the sake of updating the variables outside of function scope) is annoying. Pass A Pointer By Reference
Sometimes you need to update a pointer using a function, and so you can pass a pointer by reference. It works the same way as passing a variable by reference: updating the pointer inside of the function will update the pointer in memory (so it's a global change).
Output: 5 10 10
Pass A Pointer By Pointer
A really convoluted way to change the value of a pointer after using a function is to pass a pointer to the pointer, and then dereferencing the pointer to the pointer to change the actual pointer value. Sound confusing? That's because it's dumb. Pass a pointer by reference, like in the last section, if you need too. Still, if you see someone use a ** in the function parameter and don't know what it means, then check this code out.
Output: 5 10
Bonus: Pass A String As Const Char*
Sometimes you'll see people pass a string as "const char*". It's a little weird, but it's just a pointer to a string. Here's some code explaining how it works.
Output: Size is: 7
Word is: srcmake String version: srcmake s r c m a k e Conclusion
This is a lot of information to take in, but understanding the fundamentals of memory, pointers, and references will help you write more efficient code (and understand what other people's code). It might seem like this code isn't necessary, but even using fundamental data structures likes trees and linked lists require using pointers, so you need to know them.
Like this content and want more? Feel free to look around and find another blog post that interests you. You can also contact me through one of the various social media channels.
Twitter: @srcmake Discord: srcmake#3644 Youtube: srcmake Twitch: www.twitch.tv/srcmake Github: srcmake Intro - Binary Trees and Doubly Linked Lists
A popular interview question is converting a Binary Tree to a Doubly Linked List.
A Binary Tree (BT) is a hierachical graph data structure. Here's a blog post on Trees if you've never seen one before. (Note: We don't care if it's a Binary Search Tree, it just needs to be a binary tree.) A Doubly Linked List is a data structure where nodes that hold information are sequentially chained: each node holds a pointer to the next node in the chain. Here's a blog post on Linked Lists if you're new to them. BST To Doubly Linked List: Our Algorithm
Our algorithm to convert a Binary Tree to a Double Linked List is pretty simple. We'll do an In-Order Traversal of the tree (which ends up visiting the nodes in the order: 25 12 30 100 (which is the order we want our DLL to be), and we'll keep track of the current node that we're looking at, and the previous node that we've visited.
At each step, we'll make the currentNode's left pointer point to the previousNode, and we'll make the previousNode's right pointer point to the currentNode. Simple, right? (We'll also cover one specific case where our first node becomes the "prevNode", and we have a head pointer for our linked list point to that node.) See the diagram below to see how this works. The Code (In C++)
Our code will implement the algorithm described above as one In-Order Traversal recursive function. I've also borrowed some code from previous blog posts to create/add nodes to a binary tree, and to print a linked list, so view those blog posts if you want too.
The time complexity is O(N), as we visit each node exactly once, and the space complexity is O(1), since we use no extra space (since we don't create new nodes, we just update the pointers).
Conclusion
This is a popular interview question, and tests your knowledge of two fundamental data structured (binary trees and linked lists), as well as your recursive and pointer (and reference) skill, so make sure you can write this code yourself.
Like this content and want more? Feel free to look around and find another blog post that interests you. You can also contact me through one of the various social media channels.
Twitter: @srcmake Discord: srcmake#3644 Youtube: srcmake Twitch: www.twitch.tv/srcmake Github: srcmake Introduction - What Are Linked Lists?
Arrays and Linked Lists are the two fundamental types of data structures in programming, and every other advanced data structure is some form of array or linked list (or at least borrow the concept). An array is a contiguous block of memory reserved for holding data, but linked lists contain one data point, and have a pointer to another place in memory for the next data point.
Why Use A Linked List Instead Of An Array?
So why use a Linked List instead of an array? Let's go through some reasons.
Why Linked Lists Are Good:
Why Linked Lists Are Bad (And Why Arrays Are Good):
Singly And Doubly Linked Lists
There are two types of linked lists (sort of).
A singly linked list has a single pointer from one data point to the next data point in the list.
A doubly linked list contains not only a pointer to the next data point, but also contains a pointer to the previous data point.
Linked List C++ Code (Creation and Traversal)
Here's some code to show how Linked Lists work in C++.
The hardest thing about the code is keeping track of the pointers. Remember, create a new node with the new keyword. We need the node to show up on the heap.
Conclusion
Linked Lists are often overlooked in favor of arrays, stacks, queues, etc., but they're fundamental to understand and very popular in interview questions.
We'll look at some popular linked list questions in future blog posts.
Like this content and want more? Feel free to look around and find another blog post that interests you. You can also contact me through one of the various social media channels.
Twitter: @srcmake Discord: srcmake#3644 Youtube: srcmake Twitch: www.twitch.tv/srcmake Github: srcmake |
AuthorHi, I'm srcmake. I play video games and develop software. Pro-tip: Click the "DIRECTORY" button in the menu to find a list of blog posts.
License: All code and instructions are provided under the MIT License.
|