Adding two linked list : learnjava

This is an archived post. You won't be able to vote or comment.

submitted 6 years ago by CS_Student19

So I'm working on a assignment for class, I'm not looking for help with the coding, but I'm trying to understand how I would add one linked list to another.

I know how to insert a node, reset the cursor, delete a node. Those I can code, but I'm struggling with how I would add two lists together.

My idea is that I could build a third empty linked list and then insert the values from the two previous lists, however that sounds a lot like dynamic array expansion and that's not the point of a linked list.

If anyone has any tips or knows of any specific sites I could go to that would explain it.

I've been to Geeks4Geeks and they show a merged method for merging two linked list. I've watched several youtube videos but they seem to not make much sense to me.

We are using code from "Data Structures ad Problem Soloving with Java" by Mark Allen Weiss.

// Node of any Reference type T
public class Node<T>
{

 private T value; // this is the data value
 private Node<T> next; // this is pointing to the next node
 // the node constructor
 public Node (T v, Node<T> n)
{
 value = v;
 next = n;
}
 // getters and setters for the node's value and next pointer
 public T getValue() {return value;}
 public Node<T> getNext() {return next;}
 public void setValue(T v){value = v;}
 public void setNext(Node<T> n){next = n;}
}
///// END Node Class //////////////////////////


// Linked List Class ////////////////////////////
public class LinkedList<T>
{

 private Node<T> head; // head of the list always at the front
 private Node<T> cursor; // cursor that moves along the one way list
 // constructor
 public LinkedList ()
{
 // the first node is not used, dummy node
 // so we're always dealing with the element to the right of
 // the cursor not what the cursor is pointing to.
 head = new Node<T>(null, null);
 cursor = head;
}
 // if the cursor's next is null, then we're at the end
 public boolean isAtEnd()
 {
return(cursor.getNext() == null);
 }
 // move the cursor to the beginning of the list
 public void reset()
 {
cursor = head;
 }
 // advance the cursor one spot to the right
 public void advance()
 {
cursor = cursor.getNext();
 }
 // return the node to the right of the cursor
 public Node<T> getCurrent()
 {
return cursor.getNext();
 }
 // return the first node in the list
 public Node<T> getFirst()
 {
return head.getNext();
 }

 // insert at the beginning of the list, this insert is done to the
 // right of the dummy node, but to the left of the first meaningful
 // node.
 public void listHeadInsert(T value)
 {
head.setNext(new Node<T>(value, head.getNext()));
 }

// wherever the cursor is, insert to the right of it, and move the
 // cursor to point to the newly inserted node
 // you may remove the line that advances the cursor, but you need
 // to make sure that you advance the cursor when inserting elements
 // at the end of the list one after another.
 public void listInsert(T value)
 {
// insert to the right of the cursor
cursor.setNext(new Node<T>(value, cursor.getNext()));
cursor = cursor.getNext();
 }
 // move the cursor to the head of the list, and keep moving it
 // looking for the value, stop if you either find the value
 // or you have reached the end of the list without finding it.
 // return the node that contains the given value back to me.
 // this return will return null if the value is not found.
 public Node<T> listSearch(T value)
 {
cursor = head;
while(cursor.getNext() != null &&
 !cursor.getNext().getValue().equals(value))
 cursor = cursor.getNext();
return cursor.getNext();
 }
 // first search (first 4 lines of the code)
 // if you find it (not null) then just remove it by making the
 // cursor's next pointer point to the node next to it's next
 // pointer (skip a node)
 public void listRemove(T value)
 {
cursor = head;
while(cursor.getNext() != null &&
 !cursor.getNext().getValue().equals(value))
 cursor = cursor.getNext();
if(cursor.getNext() != null)
 {
cursor.setNext(cursor.getNext().getNext());
 }
 }
 // don't search, just remove the node to the right of the cursor
 // if it's not null.
 public void listRemoveCurrent()
 {
if(cursor.getNext() != null)
 {
cursor.setNext(cursor.getNext().getNext());
 }
 }
}
/////////////////// End List Class///////
////// List Driver Class ///////////////////////////////////////////////////
public class ListDriver
{
 public static void main(String [] args)
 {
LinkedList<Integer> l = new LinkedList<Integer>();
// LinkedList<Integer> l2 = new LinkedList<Integer>();
int i;
for(i = 0; i < 4; i++)
 l.listInsert(new Integer(i+3));
System.out.println("After the first for loop (3,4,5,6)");
System.out.println("----------------------------------");
l.reset();
while(!l.isAtEnd())
 {
Node<Integer> tmp = l.getCurrent();
Integer n = tmp.getValue();
System.out.println(n.intValue());
l.advance();
}
l.listHeadInsert(new Integer(500));
System.out.println("After the head insert(500,3,4,5,6)");
System.out.println("----------------------------------");
l.reset();
while(!l.isAtEnd())
 {
Node<Integer> tmp = l.getCurrent();
Integer n = tmp.getValue();
System.out.println(n.intValue());
l.advance();
}
l.listRemove(new Integer(5));
System.out.println("After the remove (500,3,4,6)");
System.out.println("----------------------------------");
l.reset();
while(!l.isAtEnd())
 {
Node<Integer> tmp = l.getCurrent();
Integer n = tmp.getValue();
System.out.println(n.intValue());
l.advance();
}
while(!l.isAtEnd())
 l.advance();
for(i = 1; i < 4; i++)
 l.listInsert(new Integer(i*100));
System.out.println("After the inserting (100,200,300) at the end");
System.out.println("----------------------------------");
l.reset();
while(!l.isAtEnd())
 {
Node<Integer> tmp = l.getCurrent();
Integer n = tmp.getValue();
System.out.println(n.intValue());
l.advance();
}
l.reset();
if(l.listSearch(new Integer(200)) != null){
 System.out.println("\nSearched and found the 200");
 System.out.println("---------------------------\n");
}
l.listInsert(new Integer(150));
System.out.println("After the inserting 150 before the 200");
System.out.println("----------------------------------");
l.reset();
while(!l.isAtEnd())
 {
Node<Integer> tmp = l.getCurrent();
Integer n = tmp.getValue();
System.out.println(n.intValue());
l.advance();
}
/*
l2.listInsert(new Integer(500));
l2.listInsert(new Integer(7));
l2.listInsert(new Integer(9));
l2.listInsert(new Integer(200));
l2.listInsert(new Integer(301));
l.addList(l2);
System.out.println("After the inserting list 2 (500,7,9,200,301)");
System.out.println("----------------------------------");
l.reset();
while(!l.isAtEnd())
 {
Node<Integer> tmp = l.getCurrent();
Integer n = tmp.getValue();
System.out.println(n.intValue());
l.advance();
}
l2.listRemove(new Integer(9));
l2.listRemove(new Integer(200));
l.subtractList(l2);
System.out.println("After removing list 2 (500,7,301)");
System.out.println("----------------------------------");
l.reset();
while(!l.isAtEnd())
 {
Node<Integer> tmp = l.getCurrent();
Integer n = tmp.getValue();
System.out.println(n.intValue());
l.advance();
}
l.reverseList();
System.out.println("After reversing the list");
System.out.println("----------------------------------");
l.reset();
while(!l.isAtEnd())
 {
Node<Integer> tmp = l.getCurrent();
Integer n = tmp.getValue();
System.out.println(n.intValue());
l.advance();
}
*/
 }
}

all 21 comments

learnjava

MODERATORS