You are not logged in. Please login at www.codechef.com to post your questions!

×

Data Structure : Linked list

Overview :
Linked List is a linear data structure .It is a collection of nodes.The nodes connect by pointer. Each node is contain two parts. data part, link part

  • Data contains the node value.
  • Link contains the address of next node.

alt text

Advantage of linked list :

  • Dynamic in nature
  • Insertion and deletion can be easily implemented.
  • Reduces the access time.

But here we discuss about the single linked list.

Single linked list Single linked list contain nodes which have a data part as well as address part which points to the next node in sequence of nodes. Before being single linked list operation we need to d

Disadvantage of linked list :

  • Random access is not allowed.
  • Memory is wastage.
  • Reverse traversing is difficult.

Applications of Linked List :

  • It is used to implement stack , queue, , graph etc.
  • Representing sparse matrix.
  • For separate chaining hash-table.

There are three types of linked list

  1. Single Linked List
  2. Double Linked List
  3. Circular Linked List

But here we discuss about Single Linked List. Single linked list contain nodes which have a data part as well as adress part which points to the next node in sequence of nodes.

Before doing Singly Linked operations we need to define structure for Single linked list.

struct node
{
  int data;
  node *next;
}*start=NULL:

Node Creation :
Algorithm : creation(data)

Step 1: Start
Step 2: Set temp = new node
Step 3: Set temp.data = data
Step 4: Set temp.next = NULL
Step 5: Return temp
Step 6: ENd


Traverse :
Algorithm: Traverse()

Step 1: Start
Step 2: Set temp = start
Step 3: while(temp!=NULL)
        print temp.data
        temp = temp.next
Step 4: End


Insertion :

Insertion at First

Algorithm : InserFirst( data)
 Step 1: Start
 Step 2: Set newn = creation(data).
 Step 3: if(start==NULL) { start  = newn; start.next = NULL; }
         else            { newn.next = start; start = newn; }
 Step 4: End.

Insertion at Middle
Algorithm : InsertMiddle(data,position)

Step 1: Start
Step 2: Set temp = start and newn = creation(data)
Step 3: for i=0 to position-2
        temp = temp.next
Step 4: Set temp1 = temp.next
Step 5: temp.next = newn
Step 6: newn.next = temp1
Step 7: End.


Deletion:

Algorithm : Delete(position)
Step 1: Start
Step 2: Set temp = start
Step 3: if(position==1)
        {
         if(start==NULL) print deletion not possible.
         else            start = start.next; free(temp);
        }

        else
        {
            for i=0 to position-2
            {
             temp = temp.next;
            }
            Set temp1  = temp.next;
            temp.next = temp1.next
            free(temp1)
        }

Step 4: End

Searching

Algorithm :
Search(data)
Step 1 : Start
Step 2 : Set temp = start, position = 0, flag = false.
Step 3 : While (temp.next!=NULL) 
         position increment;
         if(temp.data==data) 
         {
            flag = true. 
            print data is found
            break while loop;
         }
         temp = temp->next;
Step 4 : If flag = false print Not found.
Step 5 :End

Full Source Code : link

Hackerrank Problem Problem : Print the Elements of a Linked List, Insert a node at the head of a linked list, Insert a node at a specific position in a linked list, Delete a Node

asked 24 Nov '16, 01:46

rashedcs's gravatar image

1★rashedcs
4871525
accept rate: 4%

edited 24 Nov '16, 15:51

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×773

question asked: 24 Nov '16, 01:46

question was seen: 616 times

last updated: 24 Nov '16, 15:51