Linked List Part 1 - Data Structure | Learn More CSE

 Linked List -1

Data structures

Data structure s are just way to store and organize our data so that it can be used and  retrieved as per our requirements. using these can affect  the efficiency of our algorithms to a greater extent. There are many data structures that we will be going through throughout the post, linked-list are a part of them.

Introduction

A Linked-list is a Data structure used for storing collection of data. A linked-list has the following Properties:

• Successive elements are connected by pointers.
• can through or shrink in size during the execution of  a program.
• Can be made just as long as required ( until System memory exhausts)
• Does Not waste memory space (but takes some extra memory for pointers). It can allocates memory as the list grows.

Basic properties:

• Each element or node of a list is comprising of two items.

           (i)  Data   

              (ii)  Pointer

• In a Linked list ,the elements are not stored at contiguous memory locations.
• The first node of a linked list is known as Head.
• the last node of linked list is known as Tail.
• the last node has reference to None.

Types of Linked List

• Singly-Linked List :  Generally "linked list'' means a Singly linked list. Each Node Contains only one link which points to the subsequent node in the list.

• Doubly-Linked list: It's a two way linked list as each node points not only to the next pointer but also to the previous pointer.

• Circular-Linked List: There is no tail node i.e.,the next field is never none and the next field for the last node points to the head node.

• Circullar Doubly Linked List: Combination of both doubly linked list and circular linked list.
  
  
  

Node Class (Singly Linked List)

Note: The first node in linked list is known as Head pointer and the last node is referenced as Tail pointer. We must never lose the address of the head pointer as it references the starting address of the linked list and if lost, would lead to loss of the list.

Traversing the Linked List

   Let us assume that the head pointers to the first node of the list. to traverse the list we do       the following:

• Follow the Pointers.
• display the content of thee nodes (or  count) as they are traversed.
• stop when next pointer points to None.

Printing the Linked List : To print the linked list, we will start traversing the list from the beginning of the list(Head) until we reach the None pointer which will always be the tell pointer . Let us add a new function printList() to our LinkedList class.

Insertion of A Node in a Singly Linked List 

There are 3 possible cases: 

  ● Inserting a new node before the head (at the beginning). 

  ● Inserting a new node after the tail (at the end of the list). 

  ● Inserting a new node in the middle of the list (random location). 

Case 1: Insert node at the beginning: 

In this case, a new node is inserted before the current head node. Only one next pointer needs to be modified (new node’s next pointer) and it can be done in two steps:

 

 • Create a new node. Update the next pointer of the new node, to point to the current head.

• Update head pointer to point to the new node.

Python Code:

WE WILL UPDATE SOON.