write the following methods for a standard unorderd singly Linke List (JAVA) . t
ID: 3724946 • Letter: W
Question
write the following methods for a standard unorderd singly Linke List (JAVA). there is a head pointer, but no tail pointer
1 - insert the given key into the first position in the list (head)
public void insertFirst(int key)
2 - insert the given key at the end of list (there is no tail pointer)
public void insertLast( int key)
3 - insers the key1 into the position immediatly following the last instance of key2 if key2 exists in the list. otherwise, the key1 is inserted at the ned of the list
public void inserAfter(int key1, int key2)
4 - remove the given key from the list of it exists, otherwise does nothing
public void delete(int key)
5 - remove the first element (head) in the list
public void deleteFirst()
6- delete the last instance of the key in the list
public void deleteLastInstance (int key)
7- remove the last element in the list (there is no tail pointer).
public void deleteLast()
8- reverses the order of the nodes in the list. if the list is head->A->B->C, than it should be head->C->B->A, the method dos not create a new Linked List, but reverse the Nodes by manipulation the exisance list
public void reverseList()
Explanation / Answer
// Method to insert the given key into the first position in the list (head)
public void insertFirst(int key)
{
Node nptr = new Node(key, null);
size++ ;
if(first == null)
{
first = nptr;
last = first;
}
else
{
nptr.setLink(first);
first = nptr;
}
}
//Method to insert the given key at the end of list (there is no tail pointer)
public void insertLast(int key)
{
Node ptr = new Node(key,null);
size++ ;
if(first == null)
{
first = ptr;
last = first;
}
else
{
last.setLink(ptr);
last = ptr;
}
}
// There are three cases to consider when deleting a node….
Empty list
Delete the head node
Node is not in the list
// method to delete the node
public void delete(int key)
{
if(first == null) throw new RuntimeException("cannot delete");
if(first.data.equals(key) )
{
first = first.next;
return;
}
Node<int> cur = first;
Node<int> prev = null;
while(cur != null && !cur.data.equals(key) )
{
prev = cur;
cur = cur.next;
}
if(cur == null) throw new RuntimeException("cannot delete");
//delete current node
prev.next = cur.next;
}
// Method to print the list in reverse order
public static void reverseList(struct Node** ptr)
{
struct Node* prev = NULL;
struct Node* curr = *ptr;
struct Node* next;
while (curr != NULL)
{
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
*ptr = prev;
}
//Method to delete first element in the list
public void deleteFirst()
{
if(first.next==null) // if the list list is empty
{
first=null;
last=null;
}
else // if list contains elements
{
first=first.next;
last.next = first;
}
}
// Method to delete last element from a list
public void deleteLast()
{
Node prev = first; //point to first node
Node temp = first;
while (prev.getNext() != null) // traverse the node till last
{
temp = temp.getNext();
if (temp.getNext() == null) // if the node is the last node
{
prev.setNext(null); //delete by setting the ptr of previous node to null
count--;
}
prev = temp;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.