| Objectives |
|---|
| Explain the components necessary for a functional linked list |
| Use a linked list to store and retrieve data |
| Describe the difference between Javascript and lower-level language linked lists |
| Discuss the advantages and disadvantages of a singly linked list |
Linked lists are the base data structure that many more complex data structures use. If one has a solid understanding of linked lists then stacks, queues, hashtables, and binary trees should be relatively easy to learn and synthesize.
Linked lists store sequential (ordered) data in a series of "nodes". Each node in a linked list contains some value and a reference or "pointer" to the next node.
The very last node of a linked list, called the tail, has a null next node because nothing comes after it. (Most singly linked lists don't store a tail pointer, but ours is fancy.)
A little! But not 100%. Let's step back and take a closer look at arrays. Their true nature may surprise you!
Arrays store data in one continuous block of computer memory. The computer sets aside just enough memory when the array is created. You can think of your computer's memory as a giant city full of identical buildings. Using an array is like renting out a bunch of adjacent buildings.
This makes it really convenient to find all the data in an array. Your computer knows where each piece of data is stored because it knows where your array's territory starts and how big each building is. Your computer can move from one location in the array to the next about as easily as you go down the street.
On the other hand, your computer needs to know from the start exactly how many buildings you need -- how big the array will be. And, if you ever need more space, your computer has to find a new continuous block of empty buildings (free memory) that's big enough to fit the array.
But wait! You've never had to worry about array size...
Totally! In lower level computer programming languages like C, you would have to. JavaScript and Python handle array sizing and resizing for you efficiently. That's one of the reasons we love higher level programming languages.
But! in interviews it's good to know what's happening in the background, because that's the biggest difference between arrays and linked lists.
Creating a linked list is a bit like renting buildings all around the city, wherever it's convenient. Your computer knows the address of the headquarters (the head of the linked list), and each building manager has the address of the next building you own.
Linked lists don't need to be resized with one giant block of memory; they can grow with pointers to other parts of the computer's memory. You don't have to find continuous free space.
It's easier to insert into the middle of a linked list, because with an array you'd need to move every element after the insertion point over by one. It's easier with linked lists, as you'll see in the challenges.
On the other hand...
You can't quickly access a particular node in a linked list, like you can with array indices. You have to start with the head and move sequentially.
Linked lists take up a bit more space because in addition to storing the actual data, you have to store the pointers. (You have to hire building managers to keep track of where the next address is!)
It can take more time to access a full linked list, because the data living in different places can't just be read as a continuous chunk. You have to travel around the city to visit all of your buildings.
-
file systems Files are often stored in chunks, but when files grow large they may not fit in their original chunk. You can think of a file as a series of nodes with chunks of data and links to the next section of the file. (They're often actually implemented with a more complex related data structure called a B-tree.)
-
implementing stacks and queues Linked lists are a natural choice for these data structures, which need fast access to beginning or end of a list.
Take a look at the method stubs in singly-linked-list.js. There's starter code for a singly linked list object type and a node object type.
Each node stores data and the next node. The linked list stores its head and tail. The head and tail are both Nodes.
There are some very simple tests in simple-tests.js. Run the tests in your terminal with node simple-tests.js.
If you haven't yet, clone this repo. Change directories into the linked-list directory, and fill in the method stubs from singly-linked-list.js to your heart's content! Methods like delete and insertAt are reasonable interview questions.
These stretch challenges are harder interview questions. A hint for both: use two pointers to track two locations in the list.
-
Write a method to find the middle node of a linked list. Can you do this while only looping through the list once?
-
Cycles in linked lists (repeated nodes) can make them stop working for a lot of applications. Write a method to detect whether a linked list has a cycle in it.
The article below goes step by step on creating a linked list and inserting items into it. It might spoil some of today's solutions, but you can use this as a guide when dealing with linked lists and their properties: