Linked Lists Not Using Java Libraries Objectives Design and

Linked Lists (Not Using Java Libraries)

Objectives

Design and write a method to insert items into a list (head, tail, middle)

Design and write a method to remove items from a list (head, tail, middle)

Design and write a method to search for items in a list

Design and write a method to determine the size of the list and if it contains any elements

Design and implement a linked list with all the operations for a list (insert, remove, search)

Assignment Overview

This programming exercise introduces the linked lists data structure. The students must create all the necessary methods for the linked list and use the linked list in a Java program.

Name it Assignment_3_1 .

Write the Java source code necessary to build a solution for the problem below:
Create a MyLinkedList class. Create methods in the class to add an item to the head, tail, or middle of a linked list; remove an item from the head, tail, or middle of a linked list; check the size of the list; and search for an element in the list.

Create a test class to use the newly created MyLinkedList class. Add the following names in to the list: James, John, Michael, Peter, Allison, Daniel, George, Simon, Jason, and Mark. Your program should allow the user to enter a name from the console, and then search to see if the name exists in the list. CANNOT USE JAVA LIBRARIES

Solution

package singlelinkedlist;

class Node {
   protected String data;
   protected Node next;

   public Node() {
       next = null;
       data = null;
   }

   public Node(String d, Node n) {
       data = d;
       next = n;
   }

   public void setNext(Node n) {
       next = n;
   }

   public void setData(String d) {
       data = d;
   }

   public Node getNext() {
       return next;
   }

   public String getData() {
       return data;
   }
}

package singlelinkedlist;
import java.util.Scanner;


class LinkedList
{
protected Node head;
protected Node tail ;
public int size ;

public LinkedList()
{
head = null;
tail = null;
size = 0;
}
/* checking list is empty or not */
public boolean isEmpty()
{
return head == null;
}
/* retrieve the size of the list */
public int getSize()
{
return size;
}
public void insertAthead(String ele)
{
Node nodeptr = new Node(ele, null);
size++ ;
if(head == null)
{
head = nodeptr;
tail = head;
}
else
{
   nodeptr.setNext(head);
head = nodeptr;
}
}
public void insertAttail(String val)
{
Node node = new Node(val,null);
size++ ;
if(head == null)
{
head = node;
tail = head;
}
else
{
tail.setNext(node);
tail = node;
}
}
public void insertAtPos(String val , int pos)
{
Node node = new Node(val, null);
Node nodeptr = head;
pos = pos - 1 ;
for (int i = 1; i < size; i++)
{
if (i == pos)
{
Node tmp = nodeptr.getNext() ;
nodeptr.setNext(node);
node.setNext(tmp);
break;
}
nodeptr = nodeptr.getNext();
}
size++ ;
}
public void deleteAtPos(int position)
{
if (position == 1)
{
head = head.getNext();
size--;
return ;
}
if (position == size)
{
Node s = head;
Node t = head;
while (s != tail)
{
t = s;
s = s.getNext();
}
tail = t;
tail.setNext(null);
size --;
return;
}
Node node = head;
position = position - 1 ;
for (int i = 1; i < size - 1; i++)
{
if (i == position)
{
Node tmp = node.getNext();
tmp = tmp.getNext();
node.setNext(tmp);
break;
}
node = node.getNext();
}
size-- ;
}
/* Function to display elements */
public void display()
{
System.out.print(\"\ Singly nexted List = \");
if (size == 0)
{
System.out.print(\"empty\ \");
return;
}
if (head.getNext() == null)
{
System.out.println(head.getData() );
return;
}
Node headnode = head;
System.out.print(head.getData()+ \"->\");
headnode = head.getNext();
while (headnode.getNext() != null)
{
System.out.print(headnode.getData()+ \"->\");
headnode = headnode.getNext();
}
System.out.print(headnode.getData()+ \"\ \");
}

public static void main(String[] args)
{   
Scanner scanner = new Scanner(System.in);
LinkedList list = new LinkedList();
String character;
do
{
System.out.println(\"\ Single linked List Operations\ \");
System.out.println(\"1. insert at begining of the node\");
System.out.println(\"2. insert at tail of the node\");
System.out.println(\"3. insert at position of the linkedlist\");
System.out.println(\"4. delete at position of the linked list\");
System.out.println(\"5. check the list is empty\");
System.out.println(\"6. retrieve the size of the list\");
System.out.println(\"please choose the above options\");
int choice = scanner.nextInt();
switch (choice)
{
case 1 :
System.out.println(\"Enter string element to insert\");
list.insertAthead( scanner.next() );   
break;
case 2 :
System.out.println(\"Enter string element to insert\");
list.insertAttail( scanner.next() );   
break;   
case 3 :
System.out.println(\"Enter element to insert\");
String number = scanner.next() ;
System.out.println(\"please enter the position to insert\");
int position = scanner.nextInt() ;
if (position <= 1 || position > list.getSize() )
System.out.println(\"you entered position is invalid\");
else
list.insertAtPos(number, position);
break;
case 4 :
System.out.println(\"please enter the position you want to delete \");
int position1 = scanner.nextInt() ;
if (position1 < 1 || position1 > list.getSize() )
System.out.println(\"your entered position is invalid\");
else
list.deleteAtPos(position1);
break;
case 5 :
System.out.println(\"list is empty = \"+ list.isEmpty());
break;   
case 6 :
System.out.println(\"the size of the list is = \"+ list.getSize() +\" \ \");
break;   
default :
System.out.println(\"please choose correct option \");
break;   
}
list.display();//for displaying the list
System.out.println(\"do you continue or not if yes type(y)else type (n)\");
character = scanner.next();
} while (character.equals( \"Y\") || character.equals( \"y\") );   
}
}

output

Single linked List Operations

1. insert at begining of the node
2. insert at tail of the node
3. insert at position of the linkedlist
4. delete at position of the linked list
5. check the list is empty
6. retrieve the size of the list
please choose the above options
1
Enter string element to insert
mark

Singly nexted List = mark
do you continue or not if yes type(y)else type (n)
y

Single linked List Operations

1. insert at begining of the node
2. insert at tail of the node
3. insert at position of the linkedlist
4. delete at position of the linked list
5. check the list is empty
6. retrieve the size of the list
please choose the above options
1
Enter string element to insert
smith

Singly nexted List = smith->mark
do you continue or not if yes type(y)else type (n)
n