7    VisuAlgo.net / /list Login LL Stack Queue DLL Deque
Exploration Mode ▿

>

>
slow
fast
go to beginning previous frame pause play next frame go to end

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.


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.

X Esc
Next PgDn

We decide to group five related modes involving Linked List (LL, Stack, Queue, DLL, Deque) in one single visualization page. To facilitate more diversity, we randomize the selected mode upon loading this direct URL: https://visualgo.net/en/list.


However, you can use the following URL shortcuts to access individual mode directly:

  1. https://visualgo.net/en/ll,
  2. https://visualgo.net/en/stack,
  3. https://visualgo.net/en/queue,
  4. https://visualgo.net/en/dll,
  5. https://visualgo.net/en/deque.

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.

X Esc
Prev PgUp
Next PgDn

Linked List data structure is commonly taught in Computer Science (CS) undergraduate courses for a few reasons:

  1. It is a simple linear data structure,
  2. It has a range of potential applications as a list ADT e.g. student list, event list, appointment list, etc (albeit there are other more advanced data structures that can do the same (and more) applications better) or as stack/queue/deque ADTs,
  3. It has interesting corner/special cases to illustrate the need for a good implementation of a data structure,
  4. It has various customization options and thus usually this Linked List data structure is taught using Object-Oriented Programming (OOP) way.

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.

X Esc
Prev PgUp
Next PgDn

List is a sequence of items/data where positional order matter {a0, a1, ..., aN-2, aN-1}.
Common List ADT operations are:

  1. get(i) — maybe a trivial operation, return ai (0-based indexing),
  2. search(v) — decide if item/data v exists (and report its position/index)
    or not exist (and usually report non existing index -1) in the list,
  3. insert(i, v) — insert item/data v specifically at position/index i in the list, potentially shifting the items from previous positions: [i..N-1] by one position to their right to make a room,
  4. remove(i) — remove item that is specifically at position/index i in the list, potentially shifting the items from previous positions: [i+1..N-1] by one position to their left to close the gap.

Discussion: What if we want to remove item with specific value v in the list?

X Esc
Prev PgUp
Next PgDn

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

X Esc
Prev PgUp
Next PgDn

(Compact) Array is a good candidate for implementing the List ADT as it is a simple construct to handle a collection of items.


When we say compact array, we mean an array that has no gap, i.e. if there are N items in the array (that has size M, where M ≥ N), then only index [0..N-1] are occupied and other indices [N..M-1] should remain empty.


Compact Array Illustration
X Esc
Prev PgUp
Next PgDn

Let the compact array name be A with index [0..N-1] occupied with the items of the list.


get(i), just return A[i].
This simple operation will be unnecessarily complicated if the array is not compact.


search(v), we check each index i ∈ [0..N-1] one by one to see if A[i] == v.
v, if exists, can be anywhere in index [0..N-1].


insert(i, v), we shift items ∈ [i..N-1] to [i+1..N] (from backwards) and set A[i] = v.
This is so that v is inserted correctly at index i and maintain compactness.


remove(i), we shift items ∈ [i+1..N-1] to [i..N-2], overwriting old A[i].
This is to maintain compactness.

X Esc
Prev PgUp
Next PgDn

get(i) is very fast: Just one access, O(1).


search(v)
In the best case, v is found at the first position, O(1).
In the worst case, v is not found in the list and we require O(N) scan to determine that.


insert(i, v)
In the best case, insert at i = N, there is no shifting of element, O(1).
In the worst case, insert at i = 0, we shift all N elements, O(N).


remove(i)
In the best case, remove at i = N-1, there is no shifting of element, O(1).
In the worst case, remove at i = 0, we shift all N elements, O(N).

X Esc
Prev PgUp
Next PgDn

The size of the compact array M is not infinite, but a finite number. This poses a problem as the maximum size may not be known in advance in many applications.


If M is too big, then the unused spaces are wasted
If M is too small, then we will run out of space easily.


Solution: Make M a variable. So when the array is full, we create a larger array and move the elements from the old array to the new array. Thus, there is no more limits on size other than the (usually large) physical computer memory size. However, the issues of space wastage and copying/shifting items overhead are still problematic.

X Esc
Prev PgUp
Next PgDn

For fixed-size collections with known max limit of number of items that will ever be needed, i.e. the max size of M, then array is already a reasonably good data structure for List ADT implementation.


For variable-size collections with unknown size M and where dynamic operations such as insert/remove are common, a simple array is actually a poor choice of data structure.


For such applications, there are better ways.

X Esc
Prev PgUp
Next PgDn

We now introduce the Linked List data structure. It uses pointers to allow items/data to be non-contiguous in memory (that is the main difference with a simple array). The items are ordered from index 0 to index N-1 by associating item i with its neighbour item i+1 through a pointer.


Linked List Illustration
X Esc
Prev PgUp
Next PgDn

In the most basic form, a single vertex (node) in the Linked List has this structure:

struct or class Vertex { // we use either C++ struct/(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 above 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.

X Esc
Prev PgUp
Next PgDn

We also have a few additional data that we remember in this Linked List data structure. We use the default example Linked List above for illustration.

  1. The head pointer points to a0 — it is 22 above, nothing points to the head item,
  2. The tail pointer points to aN-1 — it is a6 = 89 above, nothing is after the tail item.

That's it, we only add two more extra variables in data structure.

X Esc
Prev PgUp
Next PgDn

Note that there are various subtle differences found in many Computer Science textbooks on how to implement a (Singly) Linked List e.g. (use tail pointer or not, circular or not, use dummy head item or not).


Our version in this visualization (with tail pointer, not circular, without dummy head) may not be 100% the same compared to what you learn in your class but the basic ideas should remain the same.


In this visualization, each vertex has Integer item, but this can easily be changed to any other data type as needed.

X Esc
Prev PgUp
Next PgDn

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.

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.

X Esc
Prev PgUp
Next PgDn

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. Examples:


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.

X Esc
Prev PgUp
Next PgDn

There are more cases than array version due to the nature of Linked List.


Most CS students who learn Linked List for the first time usually are not aware of all cases until they figure it out themselves when their Linked List code fail.


In this e-Lecture, we directly elaborate all cases.


For insert(i, v), there are four (legal) possibilities, i.e. item v is added to:

  1. The head (before the current first item) of the linked list, i = 0,
  2. An empty linked list (which fortunately similar to the previous case),
  3. The position beyond the last (the current tail) item of the linked list, i = N,
  4. The other positions of the linked list, i = [1..N-1].
X Esc
Prev PgUp
Next PgDn

The pseudo-code for insertion at head is simple and efficient, in O(1):

Vertex vtx = new Vertex(v) // create new vertex vtx from 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 above.


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

X Esc
Prev PgUp
Next PgDn

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

X Esc
Prev PgUp
Next PgDn

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:

Vertex vtx = new Vertex(v) // create new vertex vtx from item v
vtx.next = head // head was null before, so vtx.next remains null
head = vtx // the new vertex becomes the new head

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

X Esc
Prev PgUp
Next PgDn

With the Linked List traversal Get(i) sub-routine, we can now implement insertion in the middle of the Linked List as follows:

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(v) // create new vertex
vtx.next = aft // link this
pre.next = vtx // and this

Try Insert(3, 44) on the example Linked List above.


Also try Insert(6, 55) on the same example Linked List above. 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).

X Esc
Prev PgUp
Next PgDn

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(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 above. 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 at tail of the list?

X Esc
Prev PgUp
Next PgDn

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

X Esc
Prev PgUp
Next PgDn

For remove(i), there are three (legal) possibilities, i.e. index i is:

  1. The head (the current first item) of the linked list, i = 0, it affects the head pointer
  2. The tail of the linked list, i = N-1, it affects the tail pointer
  3. The other positions of the linked list, i = [1..N-2].

Discussion: Compare this slide with Insertion Cases slide to realize the subtle differences. Is removing anything from an already empty Linked List considered 'legal'?

X Esc
Prev PgUp
Next PgDn

This case is straightforward:

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 above. 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?

X Esc
Prev PgUp
Next PgDn

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

X Esc
Prev PgUp
Next PgDn

We can implement the removal of the tail of the Linked List as follows, assuming that the Linked List has more than 1 item:

Vertex pre = head
temp = head.next
while (temp.next != null) // while my neighbor is not the tail
pre = pre.next, temp = temp.next // pre = Get(N-2), temp = Get(N-1)
pre.next = null
delete temp, tail = pre // temp = (old) tail, update tail pointer

Try RemoveTail() repeatedly on the (shorter) example Linked List above. 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.

X Esc
Prev PgUp
Next PgDn

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:

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?

X Esc
Prev PgUp
Next PgDn

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

X Esc
Prev PgUp
Next PgDn

With the Linked List traversal Get(i) sub-routine, we can now implement removal of the middle item of the Linked List as follows:

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 worst O(N) case on the example Linked List above (as i = N-1 is removal at tail that requires us to update the tail pointer, see the previous case).

X Esc
Prev PgUp
Next PgDn

get(i) is slow: O(N).


search(v)
In the best case, v is found at the first position, O(1).
In the worst case, v is not found in the list and we require O(N) scan to determine that.


insert(i, v)
In the best case, insert at i = 0 or at i = N, head and tail pointers help, O(1).
In the worst case, insert at i = N-1, we need to find the item N-2 just before the tail, O(N).


remove(i)
In the best case, remove at i = 0, head pointer helps, O(1).
In the worst case, remove at i = N-1, due to the need to update the tail pointer, O(N).

X Esc
Prev PgUp
Next PgDn

Pure (Singly) Linked List applications are surprisingly rare as the simpler resizeable compact array (vector) can do the job better, compare the Linked List version with the compact array version.


However, the basic concept of Linked List that allows the vertices to be non-contiguous in memory makes it an excellent resize-able data structure for the next two other Abstract Data Types: Stack and Queue.

X Esc
Prev PgUp
Next PgDn

Stack is a particular kind of Abstract Data Type in which the main operations on the collection are the addition of an item to the collection, known as push, only to the top of the stack and removal of an item, known as pop, only from the top of the stack.


It is known as Last-In-First-Out (LIFO) data structure, e.g. the stack of book below.


Stack Illustration
X Esc
Prev PgUp
Next PgDn

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.


Discussion: Can we use vector, a resizeable array, to implement Stack ADT efficiently?

X Esc
Prev PgUp
Next PgDn

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

X Esc
Prev PgUp
Next PgDn

Stack has a few popular textbook applications, e.g.:

  1. Bracket Matching,
  2. Postix Calculator,
  3. Infix to Postfix Conversion (not shown), etc.
X Esc
Prev PgUp
Next PgDn

Mathematical expression can get quite convoluted, e.g. {[x+2]^(2+5)-2}*(y+5).


Bracket Matching problem is a problem of checking whether all brackets in the given input are matched correctly, i.e. ( with ), [ with ] and { with }, and so on.


Bracket Matching is equally useful for checking the legality of a source code.


It turns out that we can use Stack's LIFO behavior to solve this problem.

X Esc
Prev PgUp
Next PgDn

We go through the input string character-by-character in O(N), ignoring all non-brackets.


If we encounter any open bracket character, e.g. {, [, or (, we push it into a stack.


If we encounter any close bracket character, e.g. }, ], or ), we compare the current topmost item of the stack with this close bracket character. We report 'mismatch' if the stack is empty (there is no open bracket to match this close bracket with). We also report 'mismatch' the compared characters mismatch (the last encountered open bracket does not match this current close bracket) — the LIFO behavior. Otherwise, we pop the topmost open bracket character from the stack and continue.


Finally, the stack must returns back to empty state after we read through the whole string, otherwise there is/are unmatched open bracket(s) left which implies that the input string is wrong.

X Esc
Prev PgUp
Next PgDn

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.


It turns out that we can also use Stack to solve this problem efficiently.

X Esc
Prev PgUp
Next PgDn

First, we create an empty stack and then we evaluate each item in the postfix expression once by one, hence O(N):

  1. If the item is an operand, we push it on the stack,
  2. If it is an operator, we pop the last two operands from the top two elements of the stack, perform the requested operation, and push the result onto the stack again.
X Esc
Prev PgUp
Next PgDn

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


Queue Illustration
X Esc
Prev PgUp
Next PgDn

If we simply use the compact array implementation for this Queue ADT with a0 is the front of the queue and aN-1 is the back of the queue, we will encounter major performance issue with the dequeue operation.


This is because insertion at the back of a compact array is fast, O(1), but removal at the front of a compact array is slow due to the need to shift items, please review this slide.

X Esc
Prev PgUp
Next PgDn

Another possible array implementation is to avoid that shifting of items during dequeue operation by having two indices: front (the index of the queue front-most item, increased after a dequeue operation) and back (the index of the queue back-most item, also increased after an enqueue operation).


Suppose we use an array of size M = 8 items and the content of our queue is as follows: [2,4,1,7,-,-,-,-] with front = 0 and back = 3.


If we call dequeue, we have [-,4,1,7,-,-,-,-], front = 0+1 = 1, and back = 3.


If we then call enqueue(5), we have [-,4,1,7,5,-,-,-], front = 1, and back = 3+1 = 4.

X Esc
Prev PgUp
Next PgDn

However, many dequeue and enqueue operations later, we may have [-,-,-,-,-,6,2,3], front = 5, and back = 7. By now, we cannot enqueue anything else albeit we have many empty spaces at the front of the array.


If we allow both front and back indices to "wrap back" to index 0 when they have reached index M-1, we effectively make the array "circular" and we can use the empty spaces.


For example, if we call enqueue(8) next, we have [8 , -,-,-,-,6,2,3], front = 5, and back = (7+1)%8 = 0.

X Esc
Prev PgUp
Next PgDn

Yet, this does not solve the main problem of array implementation: The items of the array are stored in contiguous manner in computer memory.


A few more enqueue operations later, we may have [8,10,11,12,13 , 6,2,3], front = 5, and back = 4. At this point, we cannot enqueue anything else.


We can enlarge the array, e.g. make M = 2*8 = 16, but that will entail re-copying the items from index front to back in a slow O(N) process to have [6,2,3,8,10,11,12,13,-,-,-,-,-,-,-,-,], front = 0, and back = 7.

X Esc
Prev PgUp
Next PgDn

Recall that in a Queue, we only need the two extreme ends of the List, one for insertion (enqueue) only and one for removal (dequeue) only.


If we review this slide, we see that insertion after tail and removal from head in a Singly Linked List are fast, i.e. O(1). Thus, we designate the head/tail of the Singly Linked List as the front/back of the queue, respectively. Then, as the items in a Linked List are not stored contiguously in computer memory, our Linked List can grow and shrink as needed.


In our visualization, Queue is basically a protected Singly Linked List where we can only peek at the head item, enqueue a new item to one position after the current tail, e.g. try Enqueue(random-integer), and dequeue existing item from the head, e.g. try RemoveHead() (which is essentially a dequeue operation). All operations are O(1).

X Esc
Prev PgUp
Next PgDn

Queue ADT is usually used to simulate real queues.


One important application of Queue ADT is inside the Breadth-First Search graph traversal algorithm.

X Esc
Prev PgUp
Next PgDn

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 ai with the next item ai+1, if exists. The additional prev pointer also links item ai with the previous item ai-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 of 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.

X Esc
Prev PgUp
Next PgDn

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:

Vertex temp = tail // remember tail item
tail = tail.prev // the key step :O
tail.next = null // remove this dangling reference
delete temp // remove the old tail

Now this operation is O(1). Try RemoveTail().

X Esc
Prev PgUp
Next PgDn

As we have one more pointer prev for each vertex, their values need to be updated too during each insertion or removal.


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.

X Esc
Prev PgUp
Next PgDn

Double-ended queue (often abbreviated to deque, pronounced deck) is an Abstract Data Type that generalizes a Queue, for which elements can be added to or removed only from either the front (head) or back (tail).


In our visualization, Deque is basically a protected Doubly Linked List where we can only:
search the head/tail item (peek front/back),
insert a new item to the head/tail (try InsertHead(50) or InsertTail(10)), and
remove an existing item from the head/tail (try RemoveHead() or RemoveTail()).


All operations are O(1).

X Esc
Prev PgUp
Next PgDn

Rare, TBA.

X Esc
Prev PgUp
Next PgDn

Create operation is the same for all five modes.


However there are minor differences for the search/insert/remove operations among the five modes.


For Stack, you can only peek/restricted-search, push/restricted-insert, and pop/restricted-remove from the top/head.


For Queue, you can only peek/restricted-search from the front, push/restricted-insert from the back, and pop/restricted-remove from the front.


For Deque, you can peek/restricted-search, enqueue/restricted-insert, dequeue/restricted-remove from both front/back, but not from the middle.


Single and Double Linked List do not have such restrictions.

X Esc
Prev PgUp
Next PgDn

We have reached the end of this e-Lecture.


But read ahead for a few extra challenges.

X Esc
Prev PgUp
Next PgDn

The following are the more advanced insights about Linked List:

  1. What happen if we don't store the tail pointer too?
  2. What if we use dummy head?
  3. What if the last tail item points back to the head item?
X Esc
Prev PgUp
Next PgDn

C++ STL:
list (already a Doubly Linked List)
stack
queue
deque


Java API:
LinkedList (already a Doubly Linked List)
Stack
Queue
Deque

X Esc
Prev PgUp
Next PgDn

For a few more interesting questions about this data structure, please practice on Linked List training module (no login is required, but short and of medium difficulty setting only).


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.

X Esc
Prev PgUp
Next PgDn

We also have a few programming problems that somewhat requires the usage of this Linked List, Stack, Queue, or Deque data structure: UVa 11988 - Broken Keyboard (a.k.a. Beiju Text) and Kattis - backspace.


Try them to consolidate and improve your understanding about this data structure. You are allowed to use C++ STL or Java API if that simplifies your implementation.

X Esc
Prev PgUp
Next PgDn

As the action is being carried out, each step will be described in the status panel.

X Esc
Prev PgUp
Next PgDn

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

X Esc
Prev PgUp
Next PgDn

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

Spacebar: play/pause/replay
Left/right arrows: step backward/step forward
-/+: decrease/increase speed
X Esc
Prev PgUp
Next PgDn

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.

X Esc
Prev PgUp

Create

Insert(i,v)

Remove(i)

>

Empty

Random

Random Sorted

Random Fixed Size

Go

--- User Defined List ---

Go

i = 0 (Head), specify v =

Go

i = N (After Tail), specify v =

Go

specify both i in [1..N-1] and v =

Go

Remove i = 0 (Head)

Remove i = N-1 (Tail)

specify i in [1..N-2]

Go

About Team Terms of use

About

VisuAlgo was conceptualised in 2011 by Dr Steven Halim as a tool to help his students better understand data structures and algorithms, by allowing them to learn the basics on their own and at their own pace.

VisuAlgo contains many advanced algorithms that are discussed in Dr Steven Halim's book ('Competitive Programming', co-authored with his brother Dr Felix Halim) and beyond. Today, some of these advanced algorithms visualization/animation can only be found in VisuAlgo.

Though specifically designed for National University of Singapore (NUS) students taking various data structure and algorithm classes (e.g. CS1010, CS1020, CS2010, CS2020, CS3230, and CS3230), as advocators of online learning, we hope that curious minds around the world will find these visualisations useful too.

VisuAlgo is not designed to work well on small touch screens (e.g. smartphones) from the outset due to the need to cater for many complex algorithm visualizations that require lots of pixels and click-and-drag gestures for interaction. The minimum screen resolution for a respectable user experience is 1024x768 and only the landing page is relatively mobile-friendly.

VisuAlgo is an ongoing project and more complex visualisations are still being developed.

The most exciting development is the automated question generator and verifier (the online quiz system) that allows students to test their knowledge of basic data structures and algorithms. The questions are randomly generated via some rules and students' answers are instantly and automatically graded upon submission to our grading server. This online quiz system, when it is adopted by more CS instructors worldwide, should technically eliminate manual basic data structure and algorithm questions from typical Computer Science examinations in many Universities. By setting a small (but non-zero) weightage on passing the online quiz, a CS instructor can (significantly) increase his/her students mastery on these basic questions as the students have virtually infinite number of training questions that can be verified instantly before they take the online quiz. The training mode currently contains questions for 12 visualization modules. We will soon add the remaining 8 visualization modules so that every visualization module in VisuAlgo have online quiz component.

Another active branch of development is the internationalization sub-project of VisuAlgo. We want to prepare a database of CS terminologies for all English text that ever appear in VisuAlgo system. This is a big task and requires crowdsourcing. Once the system is ready, we will invite VisuAlgo visitors to contribute, especially if you are not a native English speaker. Currently, we have also written public notes about VisuAlgo in various languages: zh, id, kr, vn, th.

Team

Project Leader & Advisor (Jul 2011-present)
Dr Steven Halim, Senior Lecturer, School of Computing (SoC), National University of Singapore (NUS)
Dr Felix Halim, Software Engineer, Google (Mountain View)

Undergraduate Student Researchers 1 (Jul 2011-Apr 2012)
Koh Zi Chun, Victor Loh Bo Huai

Final Year Project/UROP students 1 (Jul 2012-Dec 2013)
Phan Thi Quynh Trang, Peter Phandi, Albert Millardo Tjindradinata, Nguyen Hoang Duy

Final Year Project/UROP students 2 (Jun 2013-Apr 2014)
Rose Marie Tan Zhao Yun, Ivan Reinaldo

Undergraduate Student Researchers 2 (May 2014-Jul 2014)
Jonathan Irvin Gunawan, Nathan Azaria, Ian Leow Tze Wei, Nguyen Viet Dung, Nguyen Khac Tung, Steven Kester Yuwono, Cao Shengze, Mohan Jishnu

Final Year Project/UROP students 3 (Jun 2014-Apr 2015)
Erin Teo Yi Ling, Wang Zi

Final Year Project/UROP students 4 (Jun 2016-Dec 2017)
Truong Ngoc Khanh, John Kevin Tjahjadi, Gabriella Michelle, Muhammad Rais Fathin Mudzakir

List of translators who have contributed ≥100 translations can be found at statistics page.

Acknowledgements
This project is made possible by the generous Teaching Enhancement Grant from NUS Centre for Development of Teaching and Learning (CDTL).

Terms of use

VisuAlgo is free of charge for Computer Science community on earth. If you like VisuAlgo, the only payment that we ask of you is for you to tell the existence of VisuAlgo to other Computer Science students/instructors that you know =) via Facebook, Twitter, course webpage, blog review, email, etc.

If you are a data structure and algorithm student/instructor, you are allowed to use this website directly for your classes. If you take screen shots (videos) from this website, you can use the screen shots (videos) elsewhere as long as you cite the URL of this website (http://visualgo.net) and/or list of publications below as reference. However, you are NOT allowed to download VisuAlgo (client-side) files and host it on your own website as it is plagiarism. As of now, we do NOT allow other people to fork this project and create variants of VisuAlgo. Using the offline copy of (client-side) VisuAlgo for your personal usage is fine.

Note that VisuAlgo's online quiz component is by nature has heavy server-side component and there is no easy way to save the server-side scripts and databases locally. Currently, the general public can only use the 'training mode' to access these online quiz system. Currently the 'test mode' is a more controlled environment for using these randomly generated questions and automatic verification for a real examination in NUS. Other interested CS instructor should contact Steven if you want to try such 'test mode'.

List of Publications

This work has been presented briefly at the CLI Workshop at the ACM ICPC World Finals 2012 (Poland, Warsaw) and at the IOI Conference at IOI 2012 (Sirmione-Montichiari, Italy). You can click this link to read our 2012 paper about this system (it was not yet called VisuAlgo back in 2012).

This work is done mostly by my past students. The most recent final reports are here: Erin, Wang Zi, Rose, Ivan.

Bug Reports or Request for New Features

VisuAlgo is not a finished project. Dr Steven Halim is still actively improving VisuAlgo. If you are using VisuAlgo and spot a bug in any of our visualization page/online quiz tool or if you want to request for new features, please contact Dr Steven Halim. His contact is the concatenation of his name and add gmail dot com.