A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers.

Characteristics

  • A linked list is represented by a pointer to the first node of the linked list.
  • The first node is called head.
  • If the linked list is empty, then value of head is nil.
  • Each node in a list consists of at least two parts:
    • Data
    • Pointer (Reference) to the next node; and the previous node in the case of a doubly linked list.
  • The last node is called tail.

Applications

  • Implementation of stacks and queues
  • Implementation of graphs : Adjacency list representation of graphs is most popular which is uses linked list to store adjacent vertices.
  • Dynamic memory allocation : We use linked list of free blocks.
  • Maintaining directory of names
  • Performing arithmetic operations on long integers
  • Manipulation of polynomials by storing constants in the node of linked list

Structure

list.first

Returns the head node.

list.last

Returns the tail node.

list.isEmpty

Returns a Bool. True if the list is empty. False if the list has elements.

list.count

Returns a Int with the number of elements in the list.

list.append(_ element: Element)

Appends a node to the end of the list with the given element.

list.remove(_ node: Node) -> Element?

Removes the given node and returns the element.

list.removeAll()

Removes all the nodes from the list.

list.index(at index: Int) -> Element?

Returns the element at the given index.

Advantages

  • Dynamic Size
  • Ease of Insertion/Deletion

Disadvantages

  • Random access is not allowed. Elements must be accessed sequentially.
  • Extra memory space is required for the pointer(s) for each element.
  • Not cache friendly.

Singly Linked List


Doubly Linked List


References

One Comment

Leave a Reply