P2 is below package p6_linkedList; import java.util.*; public class LinkedList {
ID: 3753470 • Letter: P
Question
P2 is below
package p6_linkedList;
import java.util.*;
public class LinkedList { public Node header;
public LinkedList() { header = null; }
public final Node Search(int key) { Node current = header; while (current != null && current.item != key) { current = current.link; } return current; }
public final void Append(int newItem) { Node newNode = new Node(newItem); newNode.link = header; header = newNode; }
public final Node Remove() { Node x = header; if (header != null) { header = header.link; } return x; }
public final Node searchPrevious(int key) { if (header == null) { return header; } else { Node current = header; while (!(current.link == null) && (current.link.item != key)) { current = current.link; } return current; } }
public final void Insert(int newItem, int preKey) { Node current; Node newNode = new Node(newItem); current = Search(preKey); if (current == null) { System.out.println("there is no such preKey!"); } else { newNode.link = current.link; current.link = newNode; } }
public final void Delete(int key) { if (header == null) // The list is empty! { System.out.println("The list is empty!"); } else { if (header.item == key) // The only node in the list is to be deleted. { header = header.link; } else // The list has more than one node. { Node p = searchPrevious(key); if (p.link == null) { System.out.println("There is no such item!"); } else { p.link = p.link.link; } } } }
public final void ShowLinkedList() { if (header == null) System.out.println("The list is empty!"); else { Node current = header; System.out.printf("%1$s->", current.item); while (!(current.link == null)) { current = current.link; System.out.printf("%1$s->", current.item);
} System.out.printf("null"); System.out.println(); } } public final void PrintList() { if (header == null) { System.out.println("The list is empty!"); } else { Node current = header; System.out.println(current.item); while (!(current.link == null)) { current = current.link; System.out.println(current.item); } } } } package p6_linkedList;
import java.util.*;
public class LinkedList { public Node header;
public LinkedList() { header = null; }
public final Node Search(int key) { Node current = header; while (current != null && current.item != key) { current = current.link; } return current; }
public final void Append(int newItem) { Node newNode = new Node(newItem); newNode.link = header; header = newNode; }
public final Node Remove() { Node x = header; if (header != null) { header = header.link; } return x; }
public final Node searchPrevious(int key) { if (header == null) { return header; } else { Node current = header; while (!(current.link == null) && (current.link.item != key)) { current = current.link; } return current; } }
public final void Insert(int newItem, int preKey) { Node current; Node newNode = new Node(newItem); current = Search(preKey); if (current == null) { System.out.println("there is no such preKey!"); } else { newNode.link = current.link; current.link = newNode; } }
public final void Delete(int key) { if (header == null) // The list is empty! { System.out.println("The list is empty!"); } else { if (header.item == key) // The only node in the list is to be deleted. { header = header.link; } else // The list has more than one node. { Node p = searchPrevious(key); if (p.link == null) { System.out.println("There is no such item!"); } else { p.link = p.link.link; } } } }
public final void ShowLinkedList() { if (header == null) System.out.println("The list is empty!"); else { Node current = header; System.out.printf("%1$s->", current.item); while (!(current.link == null)) { current = current.link; System.out.printf("%1$s->", current.item);
} System.out.printf("null"); System.out.println(); } } public final void PrintList() { if (header == null) { System.out.println("The list is empty!"); } else { Node current = header; System.out.println(current.item); while (!(current.link == null)) { current = current.link; System.out.println(current.item); } } } } . What is the time complexity of deleting a node from a linked listed? Is it faster than deleting a node from an array? Why? Test program p2-1 linkedListClass, and make sure that you understand each operation in the program. 4. Write a testing class that is similar to linkedListApplication class defined in p2-1 to test program p2-2 DoubleLinkedList. Make sure that you understand each operation in the program 5.
Explanation / Answer
Please give thumbs up, thanks
3. time complexity will be O(n) where n is number of data in linked list. and it is not faster than array because in deletion in array takes o(1) time which is O(1)<=O(n) where n>=1
/**
*
* @author VISHAL
*/
class DoublelinkedList
{
protected Node start;
protected Node end ;
public int size;
/* Constructor */
public DoublelinkedList()
{
start = null;
end = null;
size = 0;
}
/* Function to check if list is empty */
public boolean isEmpty()
{
return start == null;
}
/* Function to get size of list */
public int getSize()
{
return size;
}
/* Function to insert element at begining */
public void insertAtStart(int val)
{
Node nptr = new Node(val);
if(start == null)
{
start = nptr;
end = start;
}
else
{
start.prev=nptr;
nptr.next(start);
start = nptr;
}
size++;
}
/* Function to insert element at end */
public void insertAtEnd(int val)
{
Node nptr = new Node(val);
if(start == null)
{
start = nptr;
end = start;
}
else
{
nptr.prev=end;
end.next=nptr;
end = nptr;
}
size++;
}
/* Function to insert element at position */
public void insertAtPos(int val , int pos)
{
Node nptr = new Node(val);
if (pos == 1)
{
insertAtStart(val);
return;
}
Node ptr = start;
for (int i = 2; i <= size; i++)
{
if (i == pos)
{
Node tmp = ptr.next;
ptr.next=nptr;
nptr.prev=ptr;
nptr.next=tmp;
tmp.prev(nptr);
}
ptr = ptr.next();
}
size++ ;
}
/* Function to delete node at position */
public void deleteAtPos(int pos)
{
if (pos == 1)
{
if (size == 1)
{
start = null;
end = null;
size = 0;
return;
}
start = start.next;
start.prev=null;
size--;
return ;
}
if (pos == size)
{
end = end.prev;
end.next=null;
size-- ;
}
Node ptr = start.next;
for (int i = 2; i <= size; i++)
{
if (i == pos)
{
Node p = ptr.prev;
Node n = ptr.next;
p.next=n;
n.prev=p;
size-- ;
return;
}
ptr = ptr.next;
}
}
/* Function to display status of list */
public void display()
{
System.out.print(" Doubly Linked List = ");
if (size == 0)
{
System.out.print("empty ");
return;
}
if (start.next == null)
{
System.out.println(start.Data );
return;
}
Node ptr = start;
System.out.print(start.Data+ " <-> ");
ptr = start.next;
while (ptr.next() != null)
{
System.out.print(ptr.Data+ " <-> ");
ptr = ptr.next;
}
System.out.print(ptr.Data+ " ");
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.