using class Node: public class Node { private Double data; // we assume elements
ID: 3563674 • Letter: U
Question
using class Node:
public class Node {
private Double data; // we assume elements are character strings
private Node next;
/** Creates a node with the given element and next node. */
public Node(Double s, Node n) {
data = s;
next = n;
}
/** Returns the element of this node. */
public Double getElement() {
return data;
}
/** Returns the next node of this node. */
public Node getNext() {
return next;
}
// Modifier methods:
/** Sets the element of this node. */
public void setElement(Double newElem) {
data = newElem;
}
/** Sets the next node of this node. */
public void setNext(Node newNext) {
next = newNext;
}
}
1. Concatenate: Write a JAVA program to join two links. Given two single linked lists set the last link of the first single linked list to point to the second listened list, thus joining them into one list. Do not allocate any new nodes.
2. SWAP: test function swap the will swap two adjacent elements by adjusting only the links (and not the data) using:
1. singly linked list
2. Double linked list
What is the difference between them?
3. A circular linked list is one in which the next field for the last link node of the list points to the first link node of the list. This can be useful when you wish to have a relative positioning for elements, but no concept of an absolute first or last position.
Modify the singly linked list code discussed in class to implement circular singly linked lists.
Important Note:
1. Your program should be well-structures and well-documented.
2. Indicate the expected time and space complexity of each function.
Explanation / Answer
1)public void concat(MyString list1) {
CharacterNode tail = null, pt = list1.head;
// Find the tail of the list
if (pt == null) {
} else if (pt.getNext() == null) {
tail = pt;
} else {
while (pt.getNext() != null) {
pt = pt.getNext();
}
tail = pt;
}
list1.head = concat(list1.head, tail, list1.head);
}
private static CharacterNode concat(CharacterNode lhead, CharacterNode tail, CharacterNode pt) {
// Pass in smaller list every time
// Head traverses down list till the end
// Add new node with (pt's letter, null link)
if (lhead == null) {
// If head is null, we need to add the node
lhead = new CharacterNode(pt.getCharacter(),null);
} else if (tail.getNext() == lhead) {
// If the head is past tail, stop
} else {
// Call concat on a smaller list
lhead.setNext(concat(lhead.getNext(),tail,pt));
}
return lhead;
}
Here's CharacterNode:
class CharacterNode {
private char letter;
private CharacterNode next;
public CharacterNode(char ch, CharacterNode link) {
letter = ch;
next = link;
}
public void setCharacter(char ch) {
this.letter = ch;
}
public char getCharacter() {
return letter;
}
public void setNext(CharacterNode next) {
this.next = next;
}
public CharacterNode getNext() {
return next;
}
}
class MyString {
// member variable pointing to the head of the linked list
private CharacterNode head;
// default constructor
public MyString() {
}
// copy constructor
public MyString(MyString l) {
}
// constructor from a String
public MyString(String s) {
}
// for output purposes -- override Object version
// no spaces between the characters, no line feeds/returns
public String toString() {
}
// create a new node and add it to the head of the list
public void addHead(char ch) {
}
// create a new node and add it to the tail of the list -- "wrapper"
public void addTail(char ch) {
}
// Recursive method for addTail
private static CharacterNode addTail(CharacterNode L, char letter) {
}
// modify the list so it is reversed
public void reverse() {
}
// remove all occurrences of the character from the list -- "wrapper"
public void removeChar(char ch) {
}
// Recursive removeChar method
private static CharacterNode removeChar(CharacterNode n, char letter) {
}
// "wrapper" for recursive length()
public int length() {
}
// Returns the length of the linked list
private static int length(CharacterNode L) {
}
// concatenate a copy of list1 to the end of the list
public void concat(MyString list1) {
}
// recursive method for concat
private static CharacterNode concat(CharacterNode lhead, CharacterNode tail, CharacterNode pt) {
}
}
To concatenate two linked lists, you have to make the last node of first list to point to first node of the second list.
Node first_list = ... // head node
Node second_list = ... // head node
...
Node last_node = first_list.getLastNode()
last_node.setNext(second_list)
Now concentrate on implementing getLastNode(). It can be done very simply by using either recursion or iteration, literally in 2 lines.
2)public void switchPairs(){
if (front==null || front.next==null)
return ;
//keep a pointer to next element of front
ListNode current=front.next;
//make front point to next element
front.next=current.next;
current.next=front;
front=current;
//current has moved one step back it points to first.
//so get it to the finished swap position
current=current.next;
while(current.next!=null && current.next.next!=null){
ListNode temp = current.next.next;
current.next.next=temp.next;
temp.next=current.next;
current.next=temp;
current=temp.next;
}
}
3)
*
* Java Program to Implement Circular Singly Linked List
*/
import java.util.Scanner;
/* Class Node */
class Node
{
protected int data;
protected Node link;
/* Constructor */
public Node()
{
link = null;
data = 0;
}
/* Constructor */
public Node(int d,Node n)
{
data = d;
link = n;
}
/* Function to set link to next Node */
public void setLink(Node n)
{
link = n;
}
/* Function to set data to current Node */
public void setData(int d)
{
data = d;
}
/* Function to get link to next node */
public Node getLink()
{
return link;
}
/* Function to get data from current Node */
public int getData()
{
return data;
}
}
/* Class linkedList */
class linkedList
{
protected Node start ;
protected Node end ;
public int size ;
/* Constructor */
public linkedList()
{
start = null;
end = null;
size = 0;
}
/* Function to check if list is empty */
public boolean isEmpty()
{
return start == null;
}
/* Function to get size of the list */
public int getSize()
{
return size;
}
/* Function to insert element at the begining */
public void insertAtStart(int val)
{
Node nptr = new Node(val,null);
nptr.setLink(start);
if(start == null)
{
start = nptr;
nptr.setLink(start);
end = start;
}
else
{
end.setLink(nptr);
start = nptr;
}
size++ ;
}
/* Function to insert element at end */
public void insertAtEnd(int val)
{
Node nptr = new Node(val,null);
nptr.setLink(start);
if(start == null)
{
start = nptr;
nptr.setLink(start);
end = start;
}
else
{
end.setLink(nptr);
end = nptr;
}
size++ ;
}
/* Function to insert element at position */
public void insertAtPos(int val , int pos)
{
Node nptr = new Node(val,null);
Node ptr = start;
pos = pos - 1 ;
for (int i = 1; i < size - 1; i++)
{
if (i == pos)
{
Node tmp = ptr.getLink() ;
ptr.setLink( nptr );
nptr.setLink(tmp);
break;
}
ptr = ptr.getLink();
}
size++ ;
}
/* Function to delete element at position */
public void deleteAtPos(int pos)
{
if (size == 1 && pos == 1)
{
start = null;
end = null;
size = 0;
return ;
}
if (pos == 1)
{
start = start.getLink();
end.setLink(start);
size--;
return ;
}
if (pos == size)
{
Node s = start;
Node t = start;
while (s != end)
{
t = s;
s = s.getLink();
}
end = t;
end.setLink(start);
size --;
return;
}
Node ptr = start;
pos = pos - 1 ;
for (int i = 1; i < size - 1; i++)
{
if (i == pos)
{
Node tmp = ptr.getLink();
tmp = tmp.getLink();
ptr.setLink(tmp);
break;
}
ptr = ptr.getLink();
}
size-- ;
}
/* Function to display contents */
public void display()
{
System.out.print(" Circular Singly Linked List = ");
Node ptr = start;
if (size == 0)
{
System.out.print("empty ");
return;
}
if (start.getLink() == start)
{
System.out.print(start.getData()+ "->"+ptr.getData()+ " ");
return;
}
System.out.print(start.getData()+ "->");
ptr = start.getLink();
while (ptr.getLink() != start)
{
System.out.print(ptr.getData()+ "->");
ptr = ptr.getLink();
}
System.out.print(ptr.getData()+ "->");
ptr = ptr.getLink();
System.out.print(ptr.getData()+ " ");
}
}
/* Class CircularSinglyLinkedList */
public class CircularSinglyLinkedList
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
/* Creating object of linkedList */
linkedList list = new linkedList();
System.out.println("Circular Singly Linked List Test ");
char ch;
/* Perform list operations */
do
{
System.out.println(" Circular Singly Linked List Operations ");
System.out.println("1. insert at begining");
System.out.println("2. insert at end");
System.out.println("3. insert at position");
System.out.println("4. delete at position");
System.out.println("5. check empty");
System.out.println("6. get size");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
list.insertAtStart( scan.nextInt() );
break;
case 2 :
System.out.println("Enter integer element to insert");
list.insertAtEnd( scan.nextInt() );
break;
case 3 :
System.out.println("Enter integer element to insert");
int num = scan.nextInt() ;
System.out.println("Enter position");
int pos = scan.nextInt() ;
if (pos <= 1 || pos > list.getSize() )
System.out.println("Invalid position ");
else
list.insertAtPos(num, pos);
break;
case 4 :
System.out.println("Enter position");
int p = scan.nextInt() ;
if (p < 1 || p > list.getSize() )
System.out.println("Invalid position ");
else
list.deleteAtPos(p);
break;
case 5 :
System.out.println("Empty status = "+ list.isEmpty());
break;
case 6 :
System.out.println("Size = "+ list.getSize() +" ");
break;
default :
System.out.println("Wrong Entry ");
break;
}
/* Display List */
list.display();
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.