Linked list

From Simple English Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In computer science, a linked list is a data structure that is a linear collection of items whose order is not given by their physical placement in memory. Instead, each item links to the next item. The last item links to a terminator used to mark the end of the list.

Types of linked lists[change | change source]

Singly linked list[change | change source]

Singly-linked-list.svg
A singly linked list whose items have two fields: a value and a link to the next item

Doubly linked list[change | change source]

Doubly-linked-list.svg
A doubly linked list whose items have three fields: a value, the link forward to the next item, and the link backward to the previous item

Circular linked list[change | change source]

Circularly-linked-list.svg
A circular linked list

Linked list algorithms[change | change source]

Reversing a singly linked list[change | change source]

Item reverseList(Item head) {
    Item prev = null;
    Item curr = head;
    while (curr != null) {
        Item following = curr.next;
        curr.next = prev;
        prev = curr;
        curr = following;
    }
    return prev;
}