Definition of Linked List, conception of Node, and understanding basic terminologies

Shibaji Paul
A free video tutorial from Shibaji Paul
Programming Instructor with 16+ years of experience
4.5 instructor rating • 7 courses • 27,548 students

Lecture description

Understanding the definition of Linked List, conception of Node in a Linked List, how the link works. The external pointers for accessing linked list.

Learn more from the full course

Fundamental Data Structures & Algorithms using C language.

Learn Data Structures and algorithms for Stack, Queue, Linked List, Binary Search Tree and Heap ( using C Programming ).

15:39:49 of on-demand video • Updated April 2020

  • Recursion, Stack, Polish Notations, infix to postfix, FIFO Queue, Circular Queue, Double Ended Queue, Linked List - Linear, double and Circular - all operations, Stack and Queue using Linked List
  • What is stack, algorithms for Push and Pop operation. Implementation of Stack data structure using C.
  • Using Stack - checking parenthesis in an expression
  • Using Stack - Understanding Polish notations, algorithm and implementation of infix to postfix conversion and evaluation of postfix expression
  • What is a FIFO Queue, understanding Queue operations - Insert and delete, implementing FIFO Queue
  • Limitations of FIFO queue, concept of Circular Queue - Implementation of Circular queue.
  • Concept of Double ended queue, logic development and implementation of double ended queue.
  • Concept of Linked List - definition, why we need linked list.
  • Singly Linked List - developing algorithms for various methods and then implementing them using C programming
  • Doubly Linked List - developing algorithm of various methods and then implementing them using C programming
  • Circular Linked List - developing algorithm of various methods and then implementing them using C programming
  • How to estimate time complexity of any algorithm. Big Oh, Big Omega and Big Theta notations.
  • Recursion, concept of Tail recursion, Recursion Vs Iteration.
  • Binary Tree, definition, traversal (in-order, pre-order and post-order), binary search tree, implementation.
  • Heap - concept, definition, almost complete binary tree, insertion into heap, heap adjust, deletion, heapify and heap sort.
English [Auto] Headier, let us not try to have an idea about the structure of legalist, how it looks like obviously in an abstract sense, and how we could build such a list, as I have already told you, that link list as a dynamic to structure where the elements are created and added as and when required basis. That means it does not need to specify the size at the beginning when you need to build a link list as you do so while creating an area in legalist, everything is just explicit. That means we as a programmer need to build it from the scratch by ourselves. It's not like an area where you could provide declaration and created. Let's try to understand this concept of building link lists dynamically, obviously with an example. In this example, I'll show you how Elementalist could be built to hold some integer data. Say you have program requests to store one integer data at this moment. Then your program will use any of the available dynamic memory allocation technique from the library, like the function call to get the required space allocated in the hip. Let us consider that three hundred is the address of these allocated space that is returned by the function and now it berstein digit there say the program wants to put ten there in this space. So here it is. Sometime later on, if your program needs another space, it can do the same thing again, just calling the mallock and get the dynamic space for another integer and put the integer there. So this time the address of the block is five hundred and the program keeps twenty, dear. And if required, again, it will do the same thing again for allocating space and assigning the required Pelletiere in the allocated space, let us call the mallock once more. So this time the address is 800 and the program keeps 30 there. All these numbers that I'm using there as addresses are actually abstract. They're real addresses could be something different. I'm just using them to make you understand the fundamental of legalist. I hope you understand this sense. OK, let's not move ahead. If your program allocates these spaces dynamically, then it will lose all of them if they are not preserved and it will not be possible to access these elements later on in the program. Hence, somehow we need to keep these addresses off each of these elements stored somewhere in ADDAE. As you must know, the name of the attic contains the best actress. And since the ad allocation is contiguous, hence the address of any element can be calculated just by a simple arithmetic that is typically called the address arithmetic. But that is unlikely to happen here as the elements are not contiguous, they are discrete, rather, in order to keep the track off elements in a linked list we typically use to terminal pointers are known as head and tell. The head pointer is used to hold the address of the first element and the tail is used to hold the address of the last element. As you can see in the figure, three hundred is the address of the first element and that is there in the hit pointer. And 800 is the address of the last element and that is kept there in the tail pointer. If the program needs to access the first element, it is easy to get the address of it from the head and access it. But what about the second and subsequent elements now like area? We are unable to calculate the address of the second element as the elements are described here. As I have already told you, adding one with the base is not going to get us the second elements address, right? If you add one with three hundred, you are not going to get five hundred. That that is of the second element here is that link in the linked list gets that importance. We give the address of each subsequent element into its immediate previous element. That means the address 500 of the second element is kept explicitly in a pointer filled of the first element and also the address. 800 of the third element is kept in a quantum field of the second. These explicit pointers they are at each element is typically called the next pointer. Each element of a linked list, therefore, consists of two things. First is data. Here it is an integer like ten, twenty, thirty and so on. The second is a point, a field that holds the address of that immediate next element. Each such element in a linked list is called and not the next pointer of last note contains null. In order to mark the end of the list, I hope you have understood clearly about the structure of linked list. Now for creating a list, we would require a head pointer to hold the address of the first node Attell pointer to hold the address of the last node and a structure node that consists of a data part and a pointer to hold the address of immediate next node. And finally, the next of the last node will always contain. Now to mark the end of the list. With this, we come to the end of this lecture. In the next lecture, I will start implementing the list and will develop the functions that we need to create and maintain a link list. Thank you for watching.