Linked List

Write a program to implement circular linked list

Pinterest LinkedIn Tumblr

Circular linked list last node point to the first node of linked list. The single linked list last node point to null value which uses to identify the end of linked list. But, the circular linked list tail node point to the head node. A circularly linked list node looks exactly the same as a linear singly linked list.

Write a program to implement circular linked list. Once the item moved to tail, it overrides the head items.

Algorithm Explanation

Circular linked list uses two methods to identify header node. The header node can be identified by using the flag or any other identifier to differentiate between other nodes.
Circular linked list is same like singly linked list.
When the node add to the head, the head pointer need to more back one place to insert at beginning.
The last element points to the first element in the circular linked list.

Source Code

package com.dsacode.DataStructre.linkedlist;
 
public class CircularLinkedList {
    private Node start;
    private int count;
 
    private static class Node {
        int data;
        Node link;
 
        public Node(int data) {
            this.data = data;
        }
 
        @SuppressWarnings("unused")
        public Node(int data, Node link) {
            this.data = data;
            this.link = link;
        }
    }
     
    public void append(int x) {
        count++;
        Node temp = new Node(x);
        if (start == null) {
            start = temp;
        } else {
            Node tp = start;
            while (tp.link != start) {
                tp = tp.link;
            }
            tp.link = temp;
        }
        temp.link = start;
    }
 
    public void addBeg(int x) {
        count++;
        Node temp = new Node(x);
        if (start == null) {
            temp.link = temp;
        } else {
            Node tp = start;
            while (tp.link != start) {
                tp = tp.link;
            }
            tp.link = temp;
            temp.link = start;
        }
        start = temp;
    }
 
    public void addAt(int pos, int x) {
        Node temp, tp;
        temp = new Node(x);
        tp = start;
        for (int i = 0; i < pos; i++) {
            if (tp.link == start)
                break;
            tp = tp.link;
        }
        temp.link = tp.link;
        tp.link = temp;
        count++;
    }
 
    public void displayList() {
        if (start == null)
            System.out.println("List is empty..");
        else {
            Node temp = start;
            while (temp.link != start) {
                System.out.print( temp.data+"->");
                temp = temp.link;
            }
            System.out.println(temp.data );
        }
        System.out.println();
    }
     
     
 
    public int deleteAt(int position) {
        Node current = start;
        Node previous = start;
        for (int i = 0; i < position; i++) {
            if (current.link == start)
                break;
            previous = current;
            current = current.link;
        }
 
        if (position == 0)
            deleteFirst();
        else
            previous.link = current.link;
        count--;
         
        return current.data;
    }
 
     
    public void deleteFirst() {
        Node temp = start;
        while (temp.link != start) {
            temp = temp.link;
        }
        temp.link = start.link;
        start = start.link;
        count--;
    }
 
    public int getCount() {
        return count;
    }
     
    public static void main(String args[]){
        CircularLinkedList ccl=new CircularLinkedList();
        System.out.println("Insert items in the circular linked list: 41, 25, 63, 84");
        ccl.addBeg(41);
        ccl.append(25);
        ccl.append(63);
        ccl.append(84);
        ccl.displayList();
         
         
        System.out.println("Insert item at 2nd position: 10");
        ccl.addAt(1, 10);
        ccl.displayList();
         
         
        System.out.println("Insert item in the circular linked list: 53, 12");
        ccl.append(53);
        ccl.append(12);
        ccl.displayList();
         
        System.out.println("Delete the item in the position 1:"+ccl.deleteAt(1)+"\n"); //index starts from zero
        System.out.println("Linked List items:");
        ccl.displayList();
    }
     
}

Output

Insert items in the circular linked list: 41, 25, 63, 84
41->25->63->84
 
Insert item at 2nd position: 10
41->25->10->63->84
 
Insert item in the circular linked list: 53, 12
41->25->10->63->84->53->12
 
Delete the item in the position 1:25
 
Linked List items:
41->10->63->84->53->12

Source Explanation

Circular linked list iterate the elements from start node and tail is equal to start node.
Delete operation check current link node is equal to start node to delete the node
Add operation add the element to the beginning, particular position and add the end of linked list

Real Applications

  1. Corners of a polygon
  2. Pool of buffers that are used and released in FIFO (“first in, first out”) order.
  3. Set of processes that should be time-shared in round-robin order.

Reference

  1. http://cslibrary.stanford.edu/103/LinkedListBasics.pdf
  2. http://www.di.ubi.pt/~cbarrico/Disciplinas/DataStructures/Download/Circular_Linked_List.pdf
  3. http://www.martinbroadhurst.com/articles/circular-linked-list.html

32 Comments

  1. This paragraph will help the internet visitors for setting up new blog or even a weblog from start to end. Willetta Darrick McTyre

  2. Its not my first time to pay a visit this site, i am browsing this web site dailly and take fastidious information from here everyday. Catie Uriah Elma

  3. As I website possessor I believe the articles here is rattling superb, regards for your efforts. Pegeen Ringo Rozek

  4. This tutorial is sequential, uncomplicated and short than makes excellent perception to begin Finding out SAPUI5. Oneida Wittie Belter

  5. I think this is a real great post. Really looking forward to read more. Really Cool. Elvera Dwain Emalia

  6. Magnificent site. A lot of helpful info here. I am sending it to some pals ans additionally sharing in delicious. Nancie Alexis Roselyn

  7. Hola estuve observando asi como unas 2 horas en las webs hoy y no lei nada tan espectacular como tu escrito. Nollie Reider Riobard

  8. I am truly grateful to the holder of this website who has shared this fantastic paragraph at at this time. Cristine Marvin Ginsberg

  9. Very handful of web-sites that happen to become comprehensive beneath, from our point of view are undoubtedly properly worth checking out. Doti Eberhard Laurentia

  10. Really informative post. Really looking forward to read more. Want more. Bunny Jeffie Grunenwald

  11. I was looking at some of your posts on this website and I think this website is real instructive! Continue posting . Jennilee Lonny Sollie

  12. Very good post! We are linking to this great content on our site. Keep up the good writing. Julieta Yulma Ashli

  13. Way cool! Some extremely valid points! I appreciate you penning this write-up plus the rest of the website is extremely good. Shandra Dru Pepper

  14. Good post. I learn something new and challenging on websites I stumbleupon on a daily basis. Raeann Gustavus Joella

  15. Asking questions are actually pleasant thing if you are not understanding something entirely, however this paragraph offers good understanding even. Kathi Fremont Norean

  16. Utterly indited subject matter, regards for selective information . Guglielma Ingelbert Cohleen

  17. Well I definitely liked studying it. This post provided by you is very effective for correct planning. Dulciana Salim Chesna

  18. With this Theme you can build your own portfolio details page using a page builder. Davina Kenon Hyacinthie

  19. The condition of the person seeking nursing care is the important aspect in your choice regarding a long-term care service. Lotty Raimundo Morel

  20. Hello there! This is kind of off topic but I need some guidance from an established blog. Orelia Menard Gunas

  21. I think this web site holds some real superb information for everyone :D. Anjanette Stanly Grussing

  22. My family every time say that I am wasting my time here at net, however I know I am getting experience daily by reading thes pleasant articles. Helen-Elizabeth Field Trisha

  23. Really appreciate you sharing this blog post. Really looking forward to read more. Really Great. Doris Hilly Moretta

  24. Major thanks for the blog. Really looking forward to read more. Fantastic. Dawn Hadley Sallyann

  25. Hello it’s me, I am also visiting this web site daily,
    this web page is actually good and the users are in fact sharing pleasant thoughts.

Write A Comment