Linked List

Linked List#

Contents#

Linked List#

A linked list is a dynamic linear data structure; dynamic, meaning that its size changes at runtime; and linear, meaning that data items are arranged linearly/sequentially.

Insertions and deletions are made anywhere in the linked list.

Implementations#

C#

The null pointer indicates the end of the data structure.

Requires dynamic memory allocation.

Self-referential data items

struct node {
  int data;             // names the data item
  struct node *nxt_ptr; // points to a structure of type `struct node`
};

or

typedef struct node Node; // `Node` is an alias of `struct node`
        struct node {
  int data;               // names the data item
  Node *nxt_ptr;          // points to a structure of type `Node`
}

new_ptr = (Node *)malloc(sizeof(Node));
//        ^^^^^^^^ `malloc` returns type `void *`

Linked List#

Insert node

  • at the front of the linked list

  • after a node

  • after the last node (at the end of the linked list)

Traversal begins at the head node and stops when null is reached.

class Node:
  def __init__ (self, value):
    self.value = value
    self.next  = None

class LinkedList:
  def __init__ (self):
    self.head = None

  def print_list (self):
    temp = self.head
    while (temp):
      print(temp.value, end=' ')
      temp = temp.next
  
  def add_first (self, e):
    new_node      = Node(e)
    new_node.next = self.head # point the new node to the current head
    self.head     = new_node  # make  the new node    the     new head

  def add_last (self, e):
    new_node = Node(e)     # create a new node with value `e`
    if self.head is None:  # if the linked list is empty, assign the new node to the head
      self.head = new_node
      return
    last = self.head       # if the linked list is not empty, start at the current head and traverse the linked list
    while (last.next):
      last = last.next
    last.next = new_node   # point the last node to the new node

  def delete_first (self):
    if self.head is None:
      print('the list is empty')
      return
    self.head = self.head.next

  def delete_node (self, e):
    temp = self.head               # store the current head
    if temp is not None:           # if    the current head is to be deleted...
      if temp.value == e:
        self.head = self.head.next # ...point head to the next node
        temp      = None
        return
    while temp is not None and temp.value != e: # traverse to the last node or node e
      prev = temp
      temp = temp.next
    if temp == None: # if the last node has been reached, the node e does not exist
      return

    # otherwise, node e has been found
    prev.next = temp.next # link the previous node to the next node
    temp.next = None
    temp      = None


linked_list = LinkedList()

# create nodes
linked_list.head = Node(2)
node2 = Node(4)
node3 = Node(6)
node4 = Node(8)

# link nodes
linked_list.head.next = node2
node2.next = node3
node3.next = node4

linked_list.print_list()

2 4 6 8

Circular Linked List#

A circular linked list is just a linked list in which the last node points to the first node rather than null. A circular linked list can be singly linked or doubly linked.

A circular linked list is traversed by starting at a node and ending at the first node that was already visited (i.e., the starting node).

Advantages

  • any node can serve as the starting point, and the entire list can be traversed starting from any node

  • useful for the implementation of a queue: maintain a pointer to the last inserted node, and the front of the list is obtained by taking the next node

  • circular linked lists are useful for applications which make multiple passes around the list

class Node:
  def __init__ (self, data):
    self.data = data
    self.next = None # pointer to the next node

class Circular_Linked_List:
  def __init__ (self):
    self.head = None

  def prepend_node (self, data):
    new_node = Node(data)               # generate the new node
    tmp_node = self.head                # store the current head node
    new_node.next = self.head           # point the new node to the current head node (which may or may not be empty)
    if self.head is not None:           # if the current list contains at least one node...
      while tmp_node.next != self.head: # ...traverse the list up to the node prior to the current head node
        tmp_node = tmp_node.next        #
      tmp_node.next = new_node          # ...and link this node to the current head node 
    else:
      new_node.next = new_node          # if the list is empty, link the new node to itself
    self.head = new_node                # the new node is the new head node
  
  def print_list (self):
    if self.head is not None:
      temp = self.head
      end  = False
      while not end:                    # foreach node, starting with the head node
        print(temp.data, end=' ')       #     print the node
        temp = temp.next                #     point to the next node
        if temp == self.head:           #     if the next node is the head node
          end = True                    #         stop iterating over nodes

circular_linked_list = Circular_Linked_List()
circular_linked_list.prepend_node(8)
circular_linked_list.prepend_node(6)
circular_linked_list.prepend_node(4)
circular_linked_list.prepend_node(2)
circular_linked_list.print_list()

2 4 6 8

Doubly Linked List#

A doubly linked list contains a second prev (“previous”) pointer in addition to the usual next pointer.

Advantages

  • a doubly linked list can be traversed in both the forward direction and the backward direction

  • the delete operation is efficient since each node has a pointer to its previous node (in a singly linked list, the list may need to be traversed to obtain a pointer to the previous node of a node to be deleted)

Disadvantages

  • the extra space requirement for the additional pointer

https://www.geeksforgeeks.org/given-a-linked-list-which-is-sorted-how-will-you-insert-in-sorted-way/

Contents