CE205 Data Structures¶

// A linked list node
struct Node {
    int data;
    struct Node* next;
};

class Node {
public:
    int data;
    Node* next;
};

class LinkedList {
    Node head; // head of the list

    /* Linked list Node*/
    class Node {
        int data;
        Node next;

        // Constructor to create a new node
        // Next is by default initialized
        // as null
        Node(int d)
        {
            data = d;
            next = null;
        }
    }
}

class LinkedList {
    // The first node(head) of the linked list
    // Will be an object of type Node (null by default)
    Node head;

    class Node {
        int data;
        Node next;

        // Constructor to create a new node
        Node(int d) { data = d; }
    }
}

// C program to implement a
// linked list
#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

...

...

// Driver's code
int main()
{
    struct Node* head = NULL;
    struct Node* second = NULL;
    struct Node* third = NULL;

    // allocate 3 nodes in the heap
    head = (struct Node*)malloc(sizeof(struct Node));
    second = (struct Node*)malloc(sizeof(struct Node));
    third = (struct Node*)malloc(sizeof(struct Node));

    /* Three blocks have been allocated dynamically.
    We have pointers to these three blocks as head,
    second and third
    head         second      third
        |            |           |
        |            |           |
    +---+-----+  +----+----+     +----+----+
    | # | # |    | # | # |   | # | # |
    +---+-----+  +----+----+     +----+----+

# represents any random value.
Data is random because we haven’t assigned
anything yet */


...

    head->data = 1; // assign data in first node
    head->next = second; // Link first node with
    // the second node

    /* data has been assigned to the data part of the first
    block (block pointed by the head). And next
    pointer of first block points to second.
    So they both are linked.

    head         second      third
        |            |           |
        |            |           |
    +---+---+    +----+----+     +-----+----+
    | 1 | o----->| # | # |   | # | # |
    +---+---+    +----+----+     +-----+----+
*/


...

    // assign data to second node
    second->data = 2;

    // Link second node with the third node
    second->next = third;

    /* data has been assigned to the data part of the second
    block (block pointed by second). And next
    pointer of the second block points to the third
    block. So all three blocks are linked.

    head         second      third
        |            |           |
        |            |           |
    +---+---+    +---+---+   +----+----+
    | 1 | o----->| 2 | o-----> | # | # |
    +---+---+    +---+---+   +----+----+     */


...

    third->data = 3; // assign data to third node
    third->next = NULL;

    /* data has been assigned to data part of third
    block (block pointed by third). And next pointer
    of the third block is made NULL to indicate
    that the linked list is terminated here.

    We have the linked list ready.

        head
            |
            |
        +---+---+    +---+---+   +----+------+
        | 1 | o----->| 2 | o-----> | 3 | NULL |
        +---+---+    +---+---+   +----+------+

    Note that only head is sufficient to represent
    the whole list. We can traverse the complete
    list by following next pointers. */

    return 0;
}

// C++ program to implement a
// linked list
#include <bits/stdc++.h>
using namespace std;

class Node {
public:
    int data;
    Node* next;
};

...

// Driver's code
int main()
{
    Node* head = NULL;
    Node* second = NULL;
    Node* third = NULL;

    // allocate 3 nodes in the heap
    head = new Node();
    second = new Node();
    third = new Node();

    /* Three blocks have been allocated dynamically.
    We have pointers to these three blocks as head,
    second and third
    head         second      third
        |            |           |
        |            |           |
    +---+-----+  +----+----+     +----+----+
    | # | # |    | # | # |   | # | # |
    +---+-----+  +----+----+     +----+----+

# represents any random value.
Data is random because we haven’t assigned
anything yet */

...

    head->data = 1; // assign data in first node
    head->next = second; // Link first node with
    // the second node

    /* data has been assigned to the data part of first
    block (block pointed by the head). And next
    pointer of the first block points to second.
    So they both are linked.

    head         second      third
        |            |           |
        |            |           |
    +---+---+    +----+----+     +-----+----+
    | 1 | o----->| # | # |   | # | # |
    +---+---+    +----+----+     +-----+----+
*/

...

    // assign data to second node
    second->data = 2;

    // Link second node with the third node
    second->next = third;

    /* data has been assigned to the data part of the second
    block (block pointed by second). And next
    pointer of the second block points to the third
    block. So all three blocks are linked.

    head         second      third
        |            |           |
        |            |           |
    +---+---+    +---+---+   +----+----+
    | 1 | o----->| 2 | o-----> | # | # |
    +---+---+    +---+---+   +----+----+     */

...

    third->data = 3; // assign data to third node
    third->next = NULL;

    /* data has been assigned to the data part of the third
    block (block pointed by third). And next pointer
    of the third block is made NULL to indicate
    that the linked list is terminated here.

    We have the linked list ready.

        head
            |
            |
        +---+---+    +---+---+   +----+------+
        | 1 | o----->| 2 | o-----> | 3 | NULL |
        +---+---+    +---+---+   +----+------+


    Note that only the head is sufficient to represent
    the whole list. We can traverse the complete
    list by following the next pointers. */

    return 0;
}

// This code is contributed by rathbhupendra

// A simple Java program to introduce a linked list
class LinkedList {
    Node head; // head of list

    /* Linked list Node. This inner class is made static so
    that main() can access it */
    static class Node {
        int data;
        Node next;
        Node(int d)
        {
            data = d;
            next = null;
        } // Constructor
    }

...

    /* method to create a simple linked list with 3 nodes*/
    public static void main(String[] args)
    {
        /* Start with the empty list. */
        LinkedList llist = new LinkedList();

        llist.head = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);

        /* Three nodes have been allocated dynamically.
        We have references to these three blocks as head,
        second and third

        llist.head   second          third
            |            |               |
            |            |               |
        +----+------+    +----+------+   +----+------+
        | 1 | null |     | 2 | null |    | 3 | null |
        +----+------+    +----+------+   +----+------+
    */


...

        llist.head.next = second; // Link first node with
                                // the second node

        /* Now next of the first Node refers to the second.
        So they both are linked.

        llist.head   second          third
            |            |               |
            |            |               |
        +----+------+    +----+------+   +----+------+
        | 1 | o-------->| 2 | null |     | 3 | null |
        +----+------+    +----+------+   +----+------+ */

...

        second.next
            = third; // Link second node with the third node

        /* Now next of the second Node refers to third. So
        all three nodes are linked.

        llist.head   second          third
            |            |               |
            |            |               |
        +----+------+    +----+------+   +----+------+
        | 1 | o-------->| 2 | o-------->| 3 | null |
        +----+------+    +----+------+   +----+------+ */
    }
}

// A simple C# program to introduce a linked list
using System;

public class LinkedList {
    Node head; // head of list

    /* Linked list Node. This inner class is made static so
    that main() can access it */
    public class Node {
        public int data;
        public Node next;
        public Node(int d)
        {
            data = d;
            next = null;
        } // Constructor
    }

...

    /* method to create a simple linked list with 3 nodes*/
    public static void Main(String[] args)
    {
        /* Start with the empty list. */
        LinkedList llist = new LinkedList();

        llist.head = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);

        /* Three nodes have been allocated dynamically.
        We have references to these three blocks as head,
        second and third

        llist.head   second          third
            |            |               |
            |            |               |
        +----+------+    +----+------+   +----+------+
        | 1 | null |     | 2 | null |    | 3 | null |
        +----+------+    +----+------+   +----+------+ */

...

        llist.head.next = second; // Link first node with
                                // the second node

        /* Now next of first Node refers to second. So they
            both are linked.

        llist.head   second          third
            |            |               |
            |            |               |
        +----+------+    +----+------+   +----+------+
        | 1 | o-------->| 2 | null |     | 3 | null |
        +----+------+    +----+------+   +----+------+ */

...

        second.next
            = third; // Link second node with the third node

        /* Now next of the second Node refers to third. So
        all three nodes are linked.

        llist.head   second          third
            |            |               |
            |            |               |
        +----+------+    +----+------+   +----+------+
        | 1 | o-------->| 2 | o-------->| 3 | null |
        +----+------+    +----+------+   +----+------+ */
    }
}

// This code has been contributed by 29AjayKumar

// A simple C program for
// traversal of a linked list

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};


...

// This function prints contents of linked list starting
// from the given node
void printList(struct Node* n)
{
    while (n != NULL) {
        printf(" %d ", n->data);
        n = n->next;
    }
}


...

// Driver's code
int main()
{
    struct Node* head = NULL;
    struct Node* second = NULL;
    struct Node* third = NULL;

    // allocate 3 nodes in the heap
    head = (struct Node*)malloc(sizeof(struct Node));
    second = (struct Node*)malloc(sizeof(struct Node));
    third = (struct Node*)malloc(sizeof(struct Node));


...

    head->data = 1; // assign data in first node
    head->next = second; // Link first node with second

    second->data = 2; // assign data to second node
    second->next = third;

    third->data = 3; // assign data to third node
    third->next = NULL;

    // Function call
    printList(head);

    return 0;
}

// A simple C++ program for
// traversal of a linked list

#include <bits/stdc++.h>
using namespace std;

class Node {
public:
    int data;
    Node* next;
};


...

// This function prints contents of linked list
// starting from the given node
void printList(Node* n)
{
    while (n != NULL) {
        cout << n->data << " ";
        n = n->next;
    }
}


...

// Driver's code
int main()
{
    Node* head = NULL;
    Node* second = NULL;
    Node* third = NULL;

    // allocate 3 nodes in the heap
    head = new Node();
    second = new Node();
    third = new Node();

...

    head->data = 1; // assign data in first node
    head->next = second; // Link first node with second

    second->data = 2; // assign data to second node
    second->next = third;

    third->data = 3; // assign data to third node
    third->next = NULL;

    // Function call
    printList(head);

    return 0;
}

// This is code is contributed by rathbhupendra

// A simple Java program for traversal of a linked list

class LinkedList {

    Node head; // head of list

    /* Linked list Node. This inner class is made static so
    that main() can access it */
    static class Node {

        int data;
        Node next;
        Node(int d)
        {
            this.data = d;
            next = null;
        } // Constructor
    }

...

    /* This function prints contents of linked list starting
    * from head */
    public void printList()
    {
        Node n = head;
        while (n != null) {
            System.out.print(n.data + " ");
            n = n.next;
        }
    }


...

    // Driver's code
    public static void main(String[] args)
    {
        /* Start with the empty list. */
        LinkedList llist = new LinkedList();

        llist.head = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);

...

        llist.head.next = second; // Link first node with
                                // the second node
        second.next
            = third; // Link second node with the third node

        // Function call
        llist.printList();
    }
}

// C# program for traversal of a linked list

using System;

public class LinkedList {
    Node head; // head of list

    /* Linked list Node. This inner
    class is made static so that
    main() can access it */
    public class Node {
        public int data;
        public Node next;
        public Node(int d)
        {
            data = d;
            next = null;

        } // Constructor
    }


...

    /* This function prints contents of
    linked list starting from head */
    public void printList()
    {
        Node n = head;
        while (n != null) {
            Console.Write(n.data + " ");
            n = n.next;
        }
    }


...

    // Driver's code
    public static void Main(String[] args)
    {
        /* Start with the empty list. */
        LinkedList llist = new LinkedList();

        llist.head = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);

        llist.head.next = second; // Link first node with
                                // the second node
        second.next
            = third; // Link second node with the third node

        // Function call
        llist.printList();
    }
}

/* This code contributed by PrinciRaj1992 */

 1  2  3 

// SingleLinkedList.c : This file contains the 'main' function. Program execution begins and ends there.
//

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<stdlib.h>

#define clrscr(); system("cls");


...

void insertAtBeginning(int);
void insertAtEnd(int);
void insertBetween(int, int, int);
void display();
void removeBeginning();
void removeEnd();
void removeSpecific(int);


...

struct Node
{
    int data;
    struct Node* next;
}*head = NULL;


...

void main()
{
    int choice, value, choice1, loc1, loc2;
    clrscr();

    while (1) {

        printf("\n\n****** MENU ******\n\n");
        printf("1. Insert\n");
        printf("2. Display\n"); 
        printf("3. Delete\n"); 
        printf("4. Exit\n"); 
        printf("Enter your choice : ");

        scanf("%d", &choice);


...

        switch (choice)
        {
        case 1: printf("Enter the value to be insert: ");
            scanf("%d", &value);
            while (1) {
                printf("Where you want to insert: \n"); 
                printf("1. At Beginning\n");
                printf("2. At End\n"); 
                printf("3. Between\n");
                printf("Enter your choice: ");

                scanf("%d", &choice1);

                switch (choice1)
                {
                case 1:     
                    insertAtBeginning(value);
                    break;
                case 2:     
                    insertAtEnd(value);
                    break;
                case 3:      
                    printf("Enter the two values where you want to insert: ");
                    scanf("%d%d", &loc1, &loc2);
                    insertBetween(value, loc1, loc2);
                    break;
                default:    
                    printf("\nWrong Input!! Try again!!!\n\n");
                    continue;
                }

                break;
            }
            break;

...

        case 2:     
            display();
            break;

...

        case 3:     

            printf("How do you want to Delete: \n");
            printf("1. From Beginning\n");
            printf("2. From End\n");
            printf("3. Spesific\n");
            printf("Enter your choice: ");

            scanf("%d", &choice1);

            switch (choice1){
            case 1:     
                removeBeginning();
                break;
            case 2:     
                removeEnd();
                break;
            case 3:      
                printf("Enter the value which you wanto delete: ");

                scanf("%d", &loc2);

                removeSpecific(loc2);
                break;
            default:    
                printf("\nWrong Input!! Try again!!!\n\n");
                break;
            }
            break;

...

        case 4:     
            exit(0);
        default: 
            printf("\nWrong input!!! Try again!!\n\n");
        }
    }
}

...

void insertAtBeginning(int value)
{
    struct Node* newNode;
    newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    if (head == NULL)
    {
        newNode->next = NULL;
        head = newNode;
    }
    else
    {
        newNode->next = head;
        head = newNode;
    }
    printf("\nOne node inserted!!!\n");
}

...

void insertAtEnd(int value)
{
    struct Node* newNode;
    newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;
    if (head == NULL)
        head = newNode;
    else
    {
        struct Node* temp = head;
        while (temp->next != NULL)
            temp = temp->next;
        temp->next = newNode;
    }
    printf("\nOne node inserted!!!\n");
}

...

void insertBetween(int value, int loc1, int loc2)
{
    struct Node* newNode;

    newNode = (struct Node*)malloc(sizeof(struct Node));

    newNode->data = value;
    if (head == NULL){
        newNode->next = NULL;
        head = newNode;
    }else{
        struct Node* temp = head;
        while (temp->data != loc1 && temp->data != loc2)
            temp = temp->next;
        newNode->next = temp->next;
        temp->next = newNode;
    }
    printf("\nOne node inserted!!!\n");
}

...

void removeBeginning()
{
    if (head == NULL)
        printf("\n\nList is Empty!!!");
    else
    {
        struct Node* temp = head;
        if (head->next == NULL)
        {
            head = NULL;
            free(temp);
        }
        else
        {
            head = temp->next;
            free(temp);
            printf("\nOne node deleted!!!\n\n");
        }
    }
}

...

void removeEnd()
{
    if (head == NULL)
    {
        printf("\nList is Empty!!!\n");
    }
    else
    {
        struct Node* temp1 = head, * temp2 = 0;
        if (head->next == NULL)
            head = NULL;
        else
        {
            while (temp1->next != NULL)
            {
                temp2 = temp1;
                temp1 = temp1->next;
            }
            temp2->next = NULL;
        }
        free(temp1);
        printf("\nOne node deleted!!!\n\n");
    }
}

...

void removeSpecific(int delValue)
{
    struct Node* temp1 = head, * temp2 = 0;
    while (temp1->data != delValue)
    {
        if (temp1->next == NULL) {
            printf("\nGiven node not found in the list!!!");
            return;
        }
        temp2 = temp1;
        temp1 = temp1->next;
    }
    temp2->next = temp1->next;
    free(temp1);
    printf("\nOne node deleted!!!\n\n");
}

...

void display()
{
    if (head == NULL)
    {
        printf("\nList is Empty\n");
    }
    else
    {
        struct Node* temp = head;
        printf("\n\nList elements are - \n");
        while (temp->next != NULL)
        {
            printf("%d --->", temp->data);
            temp = temp->next;
        }
        printf("%d --->NULL", temp->data);
    }
}

struct Node {
    int data;
    struct Node * next;
};

/* Initialize nodes */
struct node *last;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;

/* Allocate memory */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));

...

/* Assign data values */
one->data = 1;
two->data = 2;
three->data = 3;

/* Connect nodes */
one->next = two;
two->next = three;
three->next = one;

/* Save address of third node in last */
last = three;

int main() {
  struct Node* last = NULL;

  last = addToEmpty(last, 6);
  last = addEnd(last, 8);
  last = addFront(last, 2);

  last = addAfter(last, 10, 2);

  traverse(last);

  deleteNode(&last, 8);

  printf("\n");

  traverse(last);

  return 0;
}

// C++ code to perform circular linked list operations

#include <iostream>

using namespace std;

struct Node {
  int data;
  struct Node* next;
};

struct Node* addToEmpty(struct Node* last, int data) {
  if (last != NULL) return last;

  // allocate memory to the new node
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

  // assign data to the new node
  newNode->data = data;

  // assign last to newNode
  last = newNode;

  // create link to iteself
  last->next = last;

  return last;
}

// add node to the front
struct Node* addFront(struct Node* last, int data) {
  // check if the list is empty
  if (last == NULL) return addToEmpty(last, data);

  // allocate memory to the new node
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

  // add data to the node
  newNode->data = data;

  // store the address of the current first node in the newNode
  newNode->next = last->next;

  // make newNode as head
  last->next = newNode;

  return last;
}

// add node to the end
struct Node* addEnd(struct Node* last, int data) {
  // check if the node is empty
  if (last == NULL) return addToEmpty(last, data);

  // allocate memory to the new node
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

  // add data to the node
  newNode->data = data;

  // store the address of the head node to next of newNode
  newNode->next = last->next;

  // point the current last node to the newNode
  last->next = newNode;

  // make newNode as the last node
  last = newNode;

  return last;
}

// insert node after a specific node
struct Node* addAfter(struct Node* last, int data, int item) {
  // check if the list is empty
  if (last == NULL) return NULL;

  struct Node *newNode, *p;

  p = last->next;
  do {
  // if the item is found, place newNode after it
  if (p->data == item) {
    // allocate memory to the new node
    newNode = (struct Node*)malloc(sizeof(struct Node));

    // add data to the node
    newNode->data = data;

    // make the next of the current node as the next of newNode
    newNode->next = p->next;

    // put newNode to the next of p
    p->next = newNode;

    // if p is the last node, make newNode as the last node
    if (p == last) last = newNode;
    return last;
  }

  p = p->next;
  } while (p != last->next);

  cout << "\nThe given node is not present in the list" << endl;
  return last;
}

// delete a node
void deleteNode(Node** last, int key) {
  // if linked list is empty
  if (*last == NULL) return;

  // if the list contains only a single node
  if ((*last)->data == key && (*last)->next == *last) {
  free(*last);
  *last = NULL;
  return;
  }

  Node *temp = *last, *d;

  // if last is to be deleted
  if ((*last)->data == key) {
  // find the node before the last node
  while (temp->next != *last) temp = temp->next;

  // point temp node to the next of last i.e. first node
  temp->next = (*last)->next;
  free(*last);
  *last = temp->next;
  }

  // travel to the node to be deleted
  while (temp->next != *last && temp->next->data != key) {
  temp = temp->next;
  }

  // if node to be deleted was found
  if (temp->next->data == key) {
  d = temp->next;
  temp->next = d->next;
  free(d);
  }
}

void traverse(struct Node* last) {
  struct Node* p;

  if (last == NULL) {
  cout << "The list is empty" << endl;
  return;
  }

  p = last->next;

  do {
  cout << p->data << " ";
  p = p->next;

  } while (p != last->next);
}