Hello, I am working on different methods for linkedlist I am having a problem fi
ID: 3539099 • Letter: H
Question
Hello, I am working on different methods for linkedlist
I am having a problem figuring out how to do one of the methods.
I need to create a method that will take two linked and add (merge) the second list to the first list
If you scroll down to were I highlighted in grey this is the method that I need to finish
thanks for helping
public class LinkedList
{
Node first;
// This method adds an element to the
// beginning of the list.
// This method takes the item that needs
// to be inserted.
// This methods will be called as follows:
// LinkedList list = new LinkedList();
// list.addFirst(40);
// That adds a node containing 40 to the beginning
// of the linked list.
public void addFirst(int item)
{
// We create a node containing the element we want
// to insert, make it point to what is currently the
// first node, and finally, we change the first reference
// to point to our new node.
first = new Node(item, first);
}
public void addLast(int item)
{
if(first == null) // If the list is empty
{
// Create a node and make it the first node
first = new Node(item, null);
return; // Exit the method
}
// Create a current reference that points to the first node
Node current = first;
while(current.next != null) // While current is not the last node
{
current = current.next; // Advance current
}
// At the end of the previous loop, current
// should be the last node.
// Make the last node point to the new node, which
// will be the new last node
current.next = new Node(item, null);
}
// EXERCISE: Write this method
// It should return true if the linked list contains the given element,
// false otherwise.
public boolean contains(int item)
{
Node current = first;
while(current != null) // While we haven't reached the end of the list ...
{
// Is this the element we're looking for?
if(current.item == item)
return true;
// no? go to the next node
current = current.next;
}
// If we're here, we didn't find the element
return false;
}
// This method inserts an item into a given index
public void insertAT(int item, int index)
{
if(index==0)
{
addFirst(item);
return;
}
Node current=first;
for(int i=0; i<index-1; i++)// Make current point to element at index -1
{
current=current.next;
if(current ==null)
throw new IllegalArgumentException ("invalid Index");
}
if(current ==null)
throw new IllegalArgumentException ("invalid Index");
current.next=new Node(item, current.next);
}
// assignment: Add this method
// This mehtod should add all of the nodes in ll into
// the current list
public void addAll(LinkedList ll)
{
//hint
// go though all of the elements in ll adding
// each to the current list
// Throw exception when neccessary
Node currentSecondList ==ll.first
While(currentSecondList!-null)
{
current.SecondList = currentSecondList.next;
}
}
public void removeFirst()
{
if(first != null) // If the list is not empty ...
first = first.next; // Make the second node the first node
}
// Assignment: Write this method.
// This method should remove the last element in the list.
public void removeLast()
{
if(first == null) // If the list is empty
{
System.out.println("List is empty so their is no node to remove:");
return;
}
// Create a current reference that points to the first node
Node current = first;
while(current.next != null) // While current is not the last node
{
current = current.next; // Advance current
}
current = null; // now since current is last node
// set current to null to remove from list
}
public void remove(int item)
{
Node current= first;
Node previous = first;
while(current != null && current.item !=item)
{
previous= current;
current = current.next;
}
if(current == null)
return;
if(current==first)
first=first.next;
else
previous.next= current.next;
}
public int get(int index)
{
Node current= first;
for(int i =0; i<index; i++) // advance current "index" times
current =current.next;
if(current ==null) // If we try to go past the end of list
{
{
throw new IllegalArgumentException("invalid index");
}
}
return current.item;
}
public void removeAt(int index)
{
if(index<0)
throw new IllegalArgumentException("illegal Index");
if(index==0)
{
removeFirst();
return;
}
Node toRemove=first;
for(int i=0; i<index-1;i++) // go to the element at index-1 previous
{
toRemove= toRemove.next;
}
if(toRemove.next==null)// if we are trying to remove last element
toRemove.next=null;
else
toRemove.next= toRemove.next.next; // remove element
}
public void removeLast1()
{
if(first == null) // If the list is empty
{
System.out.println("List is empty so their is no node to remove:");
return;
}
// Create a current reference that points to the first node
Node current = first;
Node previous = first;
while(current.next != null) // While current is not the last node
{
previous =current;
current = current.next; // Advance current
}
if(previous==first)
first=null;
else
previous.next = null; // now since current is last node
// set current to null to remove from list
}
// This method print all of the elements in the linked list
public void print()
{
// Create a current reference that points to the first node
Node current = first;
while(current != null) // While we haven't reached the end of the list ...
{
System.out.println(current.item); // Print the contents of the current node
current = current.next; // Make current point to the next node
}
}
}
Explanation / Answer
This is another version of the same function which will add the items of second list into the first list but do not directly copy the same nodes to the first as the nodes will then belong to both list and as they share common memory space(as no new node is created), modifying one list may affect te other list as well. So we just traverse the second list, copy their items into new nodes and add these nodes to the first list.
// assignment: Add this method
// This mehtod should add all of the nodes in ll into
// the current list
/************************Updated by UDCSEIITB2014****************/
public void addAll(LinkedList ll) throws Exception
{
//hint
// go though all of the elements in ll adding
// each to the current list
// Throw exception when neccessary
Node current = this.first;//Node object for traversing the original first linked list
if(current == null)
throw new Exception("Empty Linked List");
//Traverse through the first list to find the last node
while(current.next != null){
current = current.next;
}
//current points to the last node after the for loop
current.next = ll.first;
Node currentSecond =ll.first;//Node object for traversing the second linked list ll
//traverse through the second linked list and add each node to the first original linked list one by one
while(currentSecond!=null)
{
Node newNode = new Node(currentSecond.item,null);//Create a new node with same item as currentSecond's item
current.next = newNode;//Add the new node to the last of first linked list
current = current.next;//Advance the current to point to the new last node of the first linked list
currentSecond = currentSecond.next;//Advance the currentSecond to point to the next node of the second linked list
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.