I've always seen articles with titles like "Inside the mind of a <super smart person or celebrity>" or something along those lines, so I decided to incorporate some concepts of Linked Lists to this (hope you liked my reference to the cheesy titles lol). Whenever I think of Linked Lists, the first word that comes to my mind is "Linked"In, which I guess is a good starting point as to how Linked Lists actually work. Just like how users in LinkedIn have connections, Linked Lists have "nodes" that connect to each other as well. A linked list is a data structure which consists of a collection of nodes connected in an order. So basically every node (highlighted in yellow) consists of an int value (holding 2 in this case) and a pointer to the next node. What is a pointer? A pointer is essentially an address in memory. So this node also consists of an address which is the location of the next node. Note that a linked list does not have continuous memory like an array, so you DO NOT have direct access to elements. So, for example, if you would want to access the third element of an array, you would write "array[2]". However, for a linked list, you would have to traverse through the linked list until you reach the third element. This is because you need the previous node to find the location of the next node. That's why its called a linked list. Because the nodes are connected or "linked" to one another. Also, there is a NULL terminator in a linked list. So when you are traversing through your list and get to NULL, you know you've reached the end of your list. Implementing a Linked ListTo implement a Linked List, you can either create a class (for C++ Object Oriented) or a struct (for C, more low level). A struct is essentially a "record" of a group of variables with similar or different data types. It is stored as a chunk of memory. In C++, you can just create a simple Node class with the two variables, int data for the value and then the pointer. How would you write a method to insert a node at the end of a Linked List? You first need to traverse through the list until you reach the end (step 1), and then change the next pointer of the last node to the node you want to insert (step 2). NOTE: For C, you have to use malloc to allocate the Node in memory; for C++, you can just use the new keyword to create an instance of the Node class. Example of Implementation in C and C++
1 Comment
|
Archives
March 2021
Topics
All
|