Linked List is a data structure consisting of a group of vertices (nodes) which together represent a sequence. Under the simplest form, each vertex is composed of a data and a reference (link) to the next vertex in the sequence. Try clicking
for a sample animation on searching a value in a (Singly) Linked List.Linked List and its variations are used as underlying data structure to implement List, Stack, Queue, and Deque ADTs (read this Wikipedia article about ADT if you are not familiar with that term).
In this visualization, we discuss (Singly) Linked List (LL) — with a single next pointer — and its two variants: Stack and Queue, and also Doubly Linked List (DLL) — with both next and previous pointers — and its variant: Deque.
Click 'Next' (on the top right)/press 'Page Down' to advance this e-Lecture slide, use the drop down list/press 'Space' to jump to a specific slide, or Click 'X' (on the bottom right)/press 'Esc' to go to Exploration mode.
Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
Please login if you are a repeated visitor or register for an (optional) free account first.
Pro-tip: Since you are not logged-in, you may be a first time visitor who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown] to advance to the next slide, [PageUp] to go back to the previous slide, [Esc] to toggle between this e-Lecture mode and exploration mode.
Another pro-tip: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2017). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (F11) to enjoy this setup. However, you can use zoom-in (Ctrl +) or zoom-out (Ctrl -) to calibrate this.
e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).
In its basic form, a single vertex (node) in the Linked List has this rough structure:
struct Vertex { // we can use either C struct or C++/Java class
int item; // the data is stored here, an integer in this example
Vertex* next; // this pointer tells us where is the next vertex
};
Using the default example Linked List [22 (head)->2->77->6->43->76->89 (tail)] for illustration, we have:
a0 with its item = 22 and its next = a1,
a1 with its item = 2 and its next = a2,
...
a6 with its item = 89 and its next = null.
Discussion: Which one is better for a C++ implementation of Linked List? struct or class? How about Java implementation?
e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).
We also have a few additional data that we remember in this Linked List data structure. We use the default example Linked List [22 (head)->2->77->6->43->76->89 (tail)] for illustration.
That's it, we only add two more extra variables in data structure.
Since we only keep the head and tail pointers, list traversal subroutine is needed to reach positions other than the head (index 0) and the tail (index N-1).
As this sub-routine is so frequently used, we will abstract it out as a function. The code below is written in C++.
Vertex* Get(int i) { // returns the vertex
Vertex* ptr = head; // we have to start from head
for (int k = 0; k < i; k++) // advance forward i time(s)
ptr = ptr->next; // the pointers are pointing to the higher index
return ptr;
}
It runs in O(N) as i can be as big as index N-2.
Compare this with array where we can access index i in O(1) time.
As we only have direct reference to the first head item and the last tail item, plus the pointers are pointing to the right (higher position/index), we can only access the rest by starting from the head item and hopping through the next pointers. On the default [22 (head)->2->77->6->43->76->89 (tail)], we have:
— found in the example above at position/index 2 (0-based indexing).
— not found in the example above, and this is only known after all N items are examined, so Search(v) has O(N) worst case time complexity.
The (C++) code for insertion at head is simple and efficient, in O(1):
Vertex* vtx = new Vertex(); // create new vertex vtx from item v
vtx->item = v;
vtx->next = head; // link this new vertex to the (old) head vertex
head = vtx; // the new vertex becomes the new head
Try
, which is insert(0, 50), on the example Linked List [22 (head)->2->77->6->43->76->89 (tail)].Discussion: What happen if we use array implementation for insertion at head of the list?
e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).
With the Linked List traversal Get(i) sub-routine, we can now implement insertion in the middle of the Linked List as follows (in C++):
Vertex* pre = Get(i-1); // traverse to (i-1)-th vertex, O(N)
aft = pre->next; // aft cannot be null, think about it
Vertex* vtx = new Vertex(); // create new vertex
vtx->item = v;
vtx->next = aft; // link this
pre->next = vtx; // and this
Try
on the example Linked List [22 (head)->2->77->6->43->76->89 (tail)].Also try
on the same example Linked List. This is a corner case: Insert at the position of tail item, shifting the tail to one position to its right.This operation is slow, O(N), due to the need for traversing the list (e.g. if i close to N-1).
If we also remember the tail pointer as with the implementation in this e-Lecture (which is advisable as it is just one additional pointer variable), we can perform insertion beyond the tail item (at i = N) efficiently, in O(1):
Vertex* vtx = new Vertex(); // this is also a C++ code
vtx->item = v; // create new vertex vtx from item v
tail->next = vtx; // just link this, as tail is the i = (N-1)-th item
tail = vtx; // now update the tail pointer
Try
, which is insert(7, 10), on the example Linked List [22 (head)->2->77->6->43->76->89 (tail)] . A common misconception is to say that this is insertion at tail. Insertion at tail element is insert(N-1, v). This insertion beyond the tail is insert(N, v).Discussion: What happen if we use array implementation for insertion beyond the tail of the list?
e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).
e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).
With the Linked List traversal Get(i) sub-routine (discussed earlier), we can now implement removal of the middle item of the Linked List as follows (in C++):
Vertex* pre = Get(i-1); // traverse to (i-1)-th vertex, O(N)
Vertex* del = pre->next, aft = del->next;
pre->next = aft; // bypass del
delete del;
Try
This is the worst O(N) case on the example above.
Note that Remove(N-1) is removal at tail that requires us to update the tail pointer, see the next case.
We can implement the removal of the tail of the Linked List as follows, assuming that the Linked List has more than 1 item (in C++):
Vertex* pre = head;
temp = head->next;
while (temp->next != null) // while my neighbor is not the tail
pre = pre->next, temp = temp->next;
pre->next = null; // alternatively: pre = Get(N-2), temp = Get(N-1)
delete temp; // temp = (old) tail
tail = pre; // update tail pointer
Try removal at head case. We prevent execution if the LL is already empty as it is an illegal case.
repeatedly on the (shorter) example Linked List [22 (head)->2->77->6 (tail)]. It will continuously working correctly up until the Linked List contains one item where the head = the tail item and we switch toActually, if we also maintain the size of the Linked List N (compare with this slide), we can use the Linked List traversal sub-routine Get(i) to implement the removal of the tail of the Linked List this way (in C++):
Vertex* pre = Get(N-2); // go to one index just before tail, O(N)
pre->next = null;
delete tail;
tail = pre; // we have access to old tail
Notice that this operation is slow, O(N), just because of the need to update the tail pointer from item N-1 backwards by one unit to item N-2 so that future insertion after tail remains correct... This deficiency will be later addressed in Doubly Linked List variant.
Discussion: What happen if we use array implementation for removal of tail of the list?
e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).
In most implementations and also in this visualization, Stack is basically a protected (Singly) Linked List where we can only peek at the head item, push a new item only to the head (insert at head), e.g. try , and pop existing item only from the head (remove from head), e.g. try . All operations are O(1).
In this visualization, we orientate the (Single) Linked List top down, with the head/tail item at the top/bottom, respectively. In the example, we have [2 (top/head)->7->5->3->1->9 (bottom/tail)].
Discussion: Can we use vector, a resizeable array, to implement Stack ADT efficiently?
e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).
e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).
e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).
Queue is another Abstract Data Type in which the items in the collection are kept in order and the main operations on the collection are the addition of items to the back position (enqueue) and removal of items from the front position (dequeue).
It is known as First-In-First-Out (FIFO) data structure as the first item to be enqueued will eventually be the first item to be dequeued, as in real life queues (see below).
As we have one more pointer prev for each vertex, their values need to be updated too during each insertion or removal. Try all these operations on example DLL [22 (head)<->2<->77<->6<->43<->76<->89 (tail)].
Try
— additional step: 22's prev pointer points to new head 50.Try
— additional step: 10's prev pointer points to old tail 89.Try
— additional step: 6's/44's prev pointers point to 44/77, respectively.Try
— set new head 2's prev pointer to null.Try
— set 89's prev pointer to 43.e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).
Python:
list for List/Stack/Queue
deque
OCaml:
List
Stack
Queue
No built-in support for Deque
e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).
Return to 'Exploration Mode' to start exploring!
Note that if you notice any bug in this visualization or if you want to request for a new visualization feature, do not hesitate to drop an email to the project leader: Dr Steven Halim via his email address: stevenhalim at gmail dot com.
创建
搜索(v)
插入(i,v)
移除(i)