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 Search(77) 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.

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:
a₀ with its item = 22 and its next = a₁,
a₁ with its item = 2 and its next = a₂,
...
a₆ 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?

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.

1. The head pointer points to a₀ — it is 22, nothing points to the head item,
2. The tail pointer points to a_N-1 — it is a₆ = 89, nothing is after the tail item.

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:

Search(77) — found in the example above at position/index 2 (0-based indexing).

Search(7) — 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.

1. 头节点（在当前第一个项目之前），i＝0，
   
2. 空链表（与先前的情况类似）
   
3. 当前链表的尾部，i＝n，
   
4. 链表的其他位置，i＝〔1…n-1〕。

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 InsertHead(50), 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?

Empty data structure is a common corner/special case that can often cause unexpected crash if not properly tested. It is legal to insert a new item into a currently empty list, i.e. at index i = 0. Fortunately, the same pseudo-code for insertion at head also works for an empty list so we can just use the same code as in this slide (with one minor change, we also need to set tail = head).

Try InsertHead(50), which is insert(0, 50), but on the empty Linked List [].

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 Insert(3, 44) on the example Linked List  [22 (head)->2->77->6->43->76->89 (tail)].

Also try Insert(6, 55) 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 InsertTail(10), 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?

This case is straightforward (written in C++):

if (head == NULL) return; // avoid crashing when SLL is empty
Vertex* temp = head; // so we can delete it later
head = head->next; // book keeping, update the head pointer
delete temp; // which is the old head

Try RemoveHead() 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. We prevent execution if the LL is already empty as it is an illegal case.

Discussion: What happen if we use array implementation for removal of head of the list?

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 Remove(5), the element at index N-2 (as N = 7 in the example [22 (head)->2->77->6->43->76->89 (tail)] .
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 RemoveTail() 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 to removal at head case. We prevent execution if the LL is already empty as it is an illegal case.

Actually, 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?

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 InsertHead(6), and pop existing item only from the head (remove from head), e.g. try RemoveHead(). 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?

1. 一些其他有趣的应用程序但没有用于教学目的。
   
2. 括号匹配，
   
3. 后缀计算器，
   

Postfix expression is a mathematical expression in: operand1 operand2 operator format which is different from what human is most comfortable at, the Infix expression: operand1 operator operand2.

For example, expression 2 3 + 4 * is the Postfix version of (2+3)*4.

In Postfix expression, we do not need brackets.

Discussion: It turns out that we can also use Stack to solve this problem efficiently.
The question is how?

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).

Doubly Linked List (DLL) is 99% the same as its Singly Linked List version. The main difference is that now each vertex contains two pointers. The next pointer is the same as in Singly Linked List version in which it links item a_i with the next item a_i+1, if exists. The additional prev pointer also links item a_i with the previous item a_i-1, if exists.

The usage of prev pointers makes it possible to move/iterate backwards at the expense of two-times memory usage requirement as now each vertex records one additional pointer. The positive side effect of this ability to move backwards is now we can address the weak removal at tail case of the Singly Linked List.

In this visualization, notice that the edges in Doubly Linked List (and later Deque) are undirected (bidirectional) edges.

The main problem of removal of the tail element in the Singly Linked List, even if we have direct access to the tail item via the tail pointer, is that we then have to update the tail pointer to point to one item just before the tail after such removal.

With Doubly Linked List ability to move backwards, we can find this item before the tail via tail->prev... Thus, we can implement removal of tail this way (in C++):

Vertex* temp = tail; // remember tail item
tail = tail->prev; // the key step to achieve O(1) performance :O
tail->next = null; // remove this dangling reference
delete temp; // remove the old tail

Now this operation is O(1). Try RemoveTail() on example DLL [22 (head)<->2<->77<->6<->43<->76<->89 (tail)].

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 InsertHead(50) — additional step: 22's prev pointer points to new head 50.

Try InsertTail(10) — additional step: 10's prev pointer points to old tail 89.

Try Insert(3, 44) — additional step: 6's/44's prev pointers point to 44/77, respectively.

Try RemoveHead() — set new head 2's prev pointer to null.

Try Remove(5) — set 89's prev pointer to 43.

1. 如果我们不存储尾部指针，会发生什么？
   
2. 如果我们使用仿真头怎么办？
3. 如果最后一个尾部项目指向头部项目呢？

• C++ STL：forward_list （单链表），堆栈 ，队列 （双链表），deque（实际上不使用双向链表，但另一种技术，看cppreference）

For a few more interesting questions about this data structure, please practice on Linked List training module (no login is required).

However, for registered users, you should login and then go to the Main Training Page to officially clear this module and such achievement will be recorded in your user account.

• 我们也有一些编程问题，在某种程度上需要使用链表、堆栈、队列或双端队列等数据结构：UVA 11988 - 破键盘（又名北菊文本）, Kattis-退格, and Kattis-整数列表.
  

Control the animation with the player controls! Keyboard shortcuts are:

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.