Join Raghavendra Dixit for an in-depth discussion in this video What is a linked list?, part of Introduction to Data Structures & Algorithms in Java.
- [Instructor] In this chapter, we'll discuss the linked list data structure. You will learn what they are, how they are implemented and what are the different types of commonly used linked lists. A linked list in simple terms is an ordered set of data elements. Such that, each element contains a link to its successor. So a linked list contains data elements and each element points to the next element. And the last element of the sequence points to a null element.
These data elements are called nodes. The linked list itself contains a reference to the first element of the list, which is called the head element. Now, let's see what a node is. A node in a linked list can be thought of as divided into two parts. One part contains the data and here data can be anything that we want to store. It may be of primitive type, like int double etcetera. Or it can be an object reference, which may point to some object.
For example, if you were maintaining a linked list of say, user objects, where the user presents a user of a system having fields like, first name, last name, e-mail, ID, etcetera. The other part of the node holds the reference to the nextNode. That is, it points to the nextNode. And if it is the last element of the sequence, as I have already told you, it points to null. So this whole structure is called linked list.
And as mentioned earlier, the linked list object contains a reference only to the head element, not to any other element, okay. Although we can access any of these elements by starting from the head element and going to the nextNode from there. Now let's write some code to create a note. In your ID, let's create a new package for this chapter. Now inside this package, let's create a new class and call it node.
Now let's declare the member variables, data and nextNode. So we write private int data, and then private node nextNode. So here we are assuming, that the data is going to be of int type. And as you can see, we have made these variables private. So to access these, we use getAs. We write it like this.
Now let's write a constructor for the new class like this. So our node class is complete and we can create objects from this class. Now let's turn our attention to our linked list.
Note: This course was created by Packt Publishing. We are pleased to host this training in our library.
- Why study data structures and algorithms?
- How to calculate the time complexity
- Using Big O notation
- Using basic sorting and search algorithms
- Searching elements in unordered arrays and ordered arrays
- Implementing a linked list in Java
- Implementing stacks using arrays
- Queues using arrays
- Binary search trees
- Representing heaps using arrays
Skill Level Intermediate
1. Introduction to Algorithms
2. Analysis of Algorithms
3. Basic Sorting and Search Algorithms
4. Linked Lists
5. Stacks and Queues
7. Binary Search Trees
8. More Sorting Algorithms
- Mark as unwatched
- Mark all as unwatched
Are you sure you want to mark all the videos in this course as unwatched?
This will not affect your course history, your reports, or your certificates of completion for this course.Cancel
Take notes with your new membership!
Type in the entry box, then click Enter to save your note.
1:30Press on any video thumbnail to jump immediately to the timecode shown.
Notes are saved with you account but can also be exported as plain text, MS Word, PDF, Google Doc, or Evernote.