Split a linked list

[kyriacos1986]

I have been asked to design a method splitMid that can be added to the LinkedList<E> class.
This method should have the following header:

public void splitMid(LinkedList<E> sublist)

and should split the given list into two sub-lists of (almost) equal sizes. Suppose myList points to the with elements 34,65,27,89 and 12. The statement myList.splitMid(sublist); should split myList into two sublists: myList --> 34,65 and 27
sublist --> 89,12

----------------------------------------------------------------------------------------

I have made the foolwing assumptions:
1)The head of a linkedlist always points to the first node.
2)Create a new head pointer for the second linkedlist.
3)Traverse through the linkedlist and find where you want to split the list and assign the pointer to that node variable midPoint and set the next pointer of previous node to null.

I have aome problems to complete this task. Any suggestions and guidelines would be appreciated.

Here is my code:

class SplitLinkedList:

import java.util.LinkedList;

public class SplitLinkedList<E> {

	public void splitMid(LinkedList<E> sublist)
	{
		Node midPoint = nodeBefore.next; // get the midpoint
		LinkedList n = new LinkedList();
		n.head = midPoint; // head pointer for the second linked list
		
		for(int i = 0; i < n.size(); ++i)
		{
			
		}
	}	

}

class TestSplitLinkedList:

import java.util.LinkedList;


public class TestSplitLinkedList<E> {

	
	public void main(String args[])
	{
		LinkedList<Integer> myList = new LinkedList<Integer>();
		SplitLinkedList sublist = new SplitLindedList();
		
		myList.addLast(34);
		myList.addLast(65);
		myList.addLast(27);
		myList.addLast(89);
		myList.addLast(12);
		
		
		myList.splitMid(sublist);
		
		
		
	}
}

[NormR1]

I have some problems to complete this task.

Please post your questions and problems.

[kyriacos1986]

Hi Norm. My main problem is how I can split the LinkedList. I thought using the % operator could you tell me your opiinion.

In addition I am receiving the followng errors:

For:

SplitLinkedList sublist = new SplitLindedList();

Multiple markers at this line
	- SplitLindedList cannot be resolved to a type
	- SplitLinkedList is a raw type. References to generic type SplitLinkedList<E> should be 
	 parameterized

For:

myList.splitMid(sublist);

The method splitMid(SplitLinkedList) is undefined for the type LinkedList<Integer>

For:

Node midPoint = nodeBefore.next;

Multiple markers at this line
	- nodeBefore cannot be resolved to a 
	 variable
	- Node cannot be resolved to a type

For:

n.head = midPoint;

head cannot be resolved or is not a field

[NormR1]

Can you post the errors as they are printed by the compiler? Your edited postings do not show the full text of the error message.

[kyriacos1986]

Exception in thread "main" java.lang.Error: Unresolved compilation problems: 
	SplitLindedList cannot be resolved to a type
	The method splitMid(SplitLinkedList) is undefined for the type LinkedList<Integer>

	at TestSplitLinkedList.main(TestSplitLinkedList.java:10)

[NormR1]

Where is the class: SplitLindedList defined?

[kyriacos1986]

Norm I meant SplitLinkedList so this is ok now. The next error is:

Exception in thread "main" java.lang.Error: Unresolved compilation problem: 
	The method splitMid(SplitLinkedList) is undefined for the type LinkedList<Integer>

	at TestSplitLinkedList.main(TestSplitLinkedList.java:19)

[NormR1]

The method splitMid(SplitLinkedList) is undefined for the type LinkedList<Integer>

What don't you understand about that message?
Where is that method defined in the LinkedList class?

[kyriacos1986]

Hi Norm I have changed quite a lot my code the last 2 days and I came up with the following code:

UnorderedLinkedList class:

import java.util.LinkedList.*;
import java.util.*;

public class UnorderedLinkedList<E extends Comparable<? super E>> extends LinkedList<E>
{
	

	public void splitMid(LinkedListClass<E> sublist)
    {
        LinkedListNode<E> current;
        LinkedListNode<E> mid;
        int i;

        if (first == null)
        {
            sublist.first = null;
            sublist.last = null;
            sublist.count = 0;
        }
        else
            if (first.link == null)
            {
                sublist.first = null;
                sublist.last = null;
                sublist.count = 0;
            }
            else
            {
                mid = first;
                current = first.link;
                i = 1;

                if (current != null)
                    current = current.link;

                while (current != null)
                {
                    mid = mid.link;
                    current = current.link;
                    i++;

                    if (current != null)
                        current = current.link;
                }

                sublist.first = mid.link;
                sublist.last = last;
                last = mid;
                last.link = null;

                sublist.count = count - i;
                count = i;
            }
         }
}

class TestSplitLinkedList:

public class TestSplitLinkedList{

	
	public static void main(String[] args) {

		UnorderedLinkedList<Integer> myList = new UnorderedLinkedList<Integer>();
		UnorderedLinkedList<Integer> sublist = new UnorderedLinkedList<Integer>();
		 
		myList.addLast(34);
		myList.addLast(65);
		myList.addLast(27);
		myList.addLast(89);
		myList.addLast(12);
		 
		 myList.splitMid(sublist);
		//myList.splitMid(sublist);
		
	

	}

}

I am receiving the following error:

Exception in thread "main" java.lang.Error: Unresolved compilation problem: 
	The method splitMid(LinkedListClass<Integer>) from the type UnorderedLinkedList<Integer> refers to the missing type LinkedListClass

	at TestSplitLinkedList.main(TestSplitLinkedList.java:22)

[NormR1]

Can you compile the program and get an error message from the compiler?
Your IDE's message is confusing.

Where is LinkedListClass defined?

[kyriacos1986]

I am using the inbuild LinkedList class Norm.
Shall I create my own linkedlist class?

[kyriacos1986]

public void splitMid(UnorderedLinkedList<E> sublist)

I have change the parameter of the method my errors now are:

Exception in thread "main" java.lang.Error: Unresolved compilation problems: 
	LinkedListNode cannot be resolved to a type
	LinkedListNode cannot be resolved to a type
	first cannot be resolved to a variable
	first cannot be resolved or is not a field
	last cannot be resolved or is not a field
	count cannot be resolved or is not a field
	first cannot be resolved to a variable
	first cannot be resolved or is not a field
	last cannot be resolved or is not a field
	count cannot be resolved or is not a field
	first cannot be resolved to a variable
	first cannot be resolved to a variable
	first cannot be resolved or is not a field
	last cannot be resolved or is not a field
	last cannot be resolved to a variable
	last cannot be resolved to a variable
	last cannot be resolved to a variable
	count cannot be resolved or is not a field
	count cannot be resolved to a variable
	count cannot be resolved to a variable

	at UnorderedLinkedList.splitMid(UnorderedLinkedList.java:11)
	at TestSplitLinkedList.main(TestSplitLinkedList.java:22)

[NormR1]

Where are all the variables/symbols in that list defined?
You must define EVERY variable and class that you use in your program.
Otherwise the compiler will give you error messages.

[NormR1]

Can you use the javac program to compile your program? Your IDE does not print out good error messages.

[kyriacos1986]

Hi Norm i hava design an implementation of a SinglyLinkedList and a splitMid method

public class SinglyLinkedList<T> 
{
    private class Node<T>
    {
        private T data;
        private Node<T> next;
 
        public Node(T data,Node<T> next)
        {
            this.data = data;
            this.next = next;
        }
 
        public T getData()
        {
            return data;
        }
 
        public Node<T> getNext()
        {
            return next;
        }
 
        public void setNext(Node<T> next)
        {
            this.next = next;
        }       
    }
 
    private Node<T> head;//head of the linked list
    private Node<T> last;
    private int size;
    private int count;
 
    public SinglyLinkedList()
    {
        head = null;
        last = null;
        size = 0;
        count = 0;
    }
 
    public String toString()
    {
        String str = "[";
 
        Node<T> curr;
 
        for (curr=head;curr!=null;curr = curr.getNext())
        {
            str = str + curr.getData();
            if (curr.getNext()!=null)
                str = str + " ";
        }
        str = str + "]";
        return str;
    }
 
    public void addFirst(T data)
    {
        Node<T> newnode = new Node<T>(data,head);
 
        head = newnode;
        size++;
        count++;
    }
 
    public void removeFirst()
    {
        Node<T> current = head;
 
        head = head.getNext(); //move head to the next element
        current.setNext(null);
    }
 
    public void addLast(T data)
    {
        Node<T> current;
 
        if (head==null)
        {
            addFirst(data);
            return;
        }
 
        current = head;
 
        while (current.getNext()!=null)
            current = current.getNext();
 
        Node<T> newnode = new Node<T>(data,null);
        
        newnode = last;
        current.setNext(newnode);
        size++;
        count++;
 
    }
 
    public void add(int index,T data)
    {
        int i;
 
        if (index>size)
            return;
 
        if (head==null)
        {
            addFirst(data);
            return;
        }
 
        //step 1
        Node<T> current;
 
        current = head;
 
        for (i=0;i<index-1;i++)
        {
            current = current.getNext();
        }
 
        //current now refers to object immediately before new node
 
        //step 2
        Node<T> newnode = new Node<T>(data,current.getNext());
 
        //step 3
 
        current.setNext(newnode);
        size++;
        count++;
    }   
 
    public void remove(int index)
    {
        if ((index<0) || (index>=size))
            return;
 
        Node<T> current,previous;
 
        current = head;
        previous = null;
 
        for (int i=0;i<index;i++)
        {
            previous = current;
            current = current.getNext();
        }
 
        if (index!=0)
            previous.setNext(current.getNext());
        else
        {
            head = head.getNext();
        }
        size--;
    }
    
    public void splitMid(SinglyLinkedList<T> sublist)
    {
        Node<T> current;
        Node<T> mid;
        int i;

        if (head == null)
        {
            sublist.head = null;
            sublist.last = null;
            sublist.count = 0;
        }
        else
            if (head.getNext() == null)
            {
                sublist.head = null;
                sublist.last = null;
                sublist.count = 0;
            }
            else
            {
                mid = head;
                current = head;
                i = 1;

                if (current != null)
                    current = current.getNext();

                while (current != null)
                {
                    mid = mid.getNext();
                    current = current.getNext();
                    i++;

                    if (current != null)
                        current = current.getNext();
                }

                sublist.head = mid.getNext();
                sublist.last = last;
                last = mid;
                last = null;

                sublist.count = count - i;
                count = i;
            }
    }
    
    
        public static void main(String[] args)
    {
        SinglyLinkedList<Integer> myList = new SinglyLinkedList<Integer>();
        SinglyLinkedList<Integer> sublist = new SinglyLinkedList<Integer>();
        myList.addLast(34);
        myList.addLast(65);
        myList.addLast(27);
        myList.addLast(89);
        myList.addLast(12);
        
        System.out.println( myList);
//         ListIterator<Integer> it = myList.listIterator();
//          while(it.hasNext())
//          {
//              System.out.println(it.next());
//          }
             
        myList.splitMid(SinglyLinkedList<T> sublist);
    }
}

I am receiving the following error for this line:

myList.splitMid(SinglyLinkedList<T> sublist);

Cannot find symbol - variable SinglyLinkedList

[NormR1]

Look at what that statement is doing?
Is it defining a method
or is it calling a method?

What is the correct syntax for what it is doing?

[kyriacos1986]

Norm thank you for your help and I hope that you had nice christmas. Here is my code and it works as I expexted.

SinglyLinkedList<T> class:

public class SinglyLinkedList<T> 
{
        private class Node<T>
    {
        private T data;
        private Node<T> next;
 
        public Node(T data,Node<T> next)
        {
            this.data = data;
            this.next = next;
        }
 
        public T getData()
        {
            return data;
        }
 
        public Node<T> getNext()
        {
            return next;
        }
 
        public void setNext(Node<T> next)
        {
            this.next = next;
        }       
    }
 
    private Node<T> head;//head of the linked list
    private Node<T> last;
    private int size;
    private int count;
 
    public SinglyLinkedList()
    {
        head = null;
        last = null;
        size = 0;
        count = 0;
    }
 
    public String toString()
    {
        String str = "[";
 
        Node<T> curr;
 
        for (curr=head;curr!=null;curr = curr.getNext())
        {
            str = str + curr.getData();
            if (curr.getNext()!=null)
                str = str + " ";
        }
        str = str + "]";
        return str;
    }
 
    public void addFirst(T data)
    {
        Node<T> newnode = new Node<T>(data,head);
 
        head = newnode;
        size++;
        count++;
    }
 
    public void removeFirst()
    {
        Node<T> current = head;
 
        head = head.getNext(); //move head to the next element
        current.setNext(null);
        count--;
    }
 
    public void addLast(T data)
    {
        Node<T> current;
 
        if (head==null)
        {
            addFirst(data);
            return;
        }
 
        current = head;
 
        while (current.getNext()!=null)
            current = current.getNext();
 
        Node<T> newnode = new Node<T>(data,null);
 
        current.setNext(newnode);
        size++;
        count++;
 
    }
 
    public void add(int index,T data)
    {
        int i;
 
        if (index>size)
            return;
 
        if (head==null)
        {
            addFirst(data);
            return;
        }
 
        //step 1
        Node<T> current;
 
        current = head;
 
        for (i=0;i<index-1;i++)
        {
            current = current.getNext();
        }
 
        //current now refers to object immediately before new node
 
        //step 2
        Node<T> newnode = new Node<T>(data,current.getNext());
 
        //step 3
 
        current.setNext(newnode);
        size++;
        count++;
    }   
 
    public void remove(int index)
    {
        if ((index<0) || (index>=size))
            return;
 
        Node<T> current,previous;
 
        current = head;
        previous = null;
 
        for (int i=0;i<index;i++)
        {
            previous = current;
            current = current.getNext();
        }
 
        if (index!=0)
            previous.setNext(current.getNext());
        else
        {
            head = head.getNext();
        }
        size--;
        count--;
    }

    
    public void splitMid(SinglyLinkedList<T> sublist)
    {
        Node<T> current;
        Node<T> mid;
        int i;

        if (head == null)
        {
            sublist.head = null;
            sublist.last = null;
            sublist.count = 0;
        }
        else
            if (head.next == null)
            {
                sublist.head = null;
                sublist.last = null;
                sublist.count = 0;
            }
            else
            {
                mid = head;
                current = head.next;
                i = 1;

                if (current != null)
                    current = current.next;

                while (current != null)
                {
                    mid = mid.next;
                    current = current.next;
                    i++;

                    if (current != null)
                        current = current.next;
                }

                sublist.head = mid.next;
                sublist.last = last;
                last = mid;
                last.next = null;

                sublist.count = count - i;
                count = i;
            }
    }
    
    
          public static void main(String[] args)
          {
              SinglyLinkedList<Integer> myList = new SinglyLinkedList<Integer>();
              SinglyLinkedList<Integer> sublist = new SinglyLinkedList<Integer>();
              myList.addLast(34);
              myList.addLast(65);
              myList.addLast(27);
              myList.addLast(89);
              myList.addLast(12);
              System.out.println("My original myList: " + myList);

             
              myList.splitMid(sublist);
        
              System.out.println("myList after calling splitMid: " + myList);
              System.out.println("sublist is: " + sublist);
          }
}

Output:

My original myList: [34 65 27 89 12]
myList after calling splitMid: [34 65 27]
sublist is: [89 12]

[NormR1]

Glad you figured it out.