Fandom

File Formats Wiki

Linked list

261pages on
this wiki
Add New Page
Talk0 Share
Implementation source code is/may be available for this article.
Smallwikipedialogo.png Wikipedia has an article related to:

A linked list is a linear list abstract data structure. It is composed of nodes which contain arbitrary data for the purpose of the linked list, and a reference or two to the next (or previous) nodes to it.

It is traversed by sequential access, but it does not allow random access. It allows quick addition of items, and searching and deletion of items by sequential access.

Linked list are also used as a base of other data structures such as a stack.

TypesEdit

  • Singly-linked lists are the simplest type of linked list, where each node contains a piece of data and a reference to the next node.
  • In Doubly-linked lists, nodes have a reference to both the next node and the previous node. Useful for backwards traversal of the list.
  • Linear linked lists are the typical type of linked list, where the list is started or terminated by a sentinel node or a null reference.
  • Circular linked list are circular in nature; the list does not end. It is similar to a linear linked list except the last node refers to the first node instead of terminating the list. In the case of doubly-linked lists, the previous node reference of the first node refers to the last node.
  • Sentinel or dummy nodes are nodes added at the beginning or the end of a linked list to simplify overall coding of the linked list. This is to ensure that every (non-sentinel) node points to a "next node" in the list.

MethodsEdit

Common methods done with a linked list are:

  • Iteration/traversal
  • Adding of an item
    • Inserting an item at an index
    • Inserting an item at the beginning
    • Inserting an item at the end
  • Get/set item at index
  • Remove item at index
  • Remove item with specific value / equal to some other item
  • Item count

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.