Thread: request

• implement doubly linked list and include a method to insert new node in the middle of the list
• implement singly linked list and include a method to check whether two single linked lists have the same contents

please help me in these program..

Originally Posted by aegr

• implement doubly linked list and include a method to insert new node in the middle of the list
• implement singly linked list and include a method to check whether two single linked lists have the same contents

please help me in these program..

These are assignment requirements and not a forum question. Surely no one is going go do your work for you, nor should they, but at present, it is quite hard to figure out exactly how to help you until you ask a specific question or two.

Originally Posted by curmudgeon

These are assignment requirements and not a forum question. Surely no one is going go do your work for you, nor should they, but at present, it is quite hard to figure out exactly how to help you until you ask a specific question or two.

i tried for the first question
but i have errors
can you help me please??

PHP Code:

import java.util.Random;
 
public class DLinkedList {

private class Node {
int item;
Node next;
Node previous;
// protected Node top;
 
}

private Node head = null;

public void Insert(int item) {
if( head==null){
head = new Node();
head.item = item;
head.next = head;
head.previous = head;
}else{
Node newNode = new Node();
newNode.item = item;
Node tail = head.previous;
tail.next = newNode;
newNode.previous = tail;
newNode.next = head;
head.previous = newNode;
}
}
public boolean insertAfter(int key, int item) {
   Node first=null;
  Node last=null;
    Node current = first;
    while (current.item !=key) {
      current = current.next;
      if (current == null){
        return false;
      }
    }
   Node newNode = new Node();

    if (current == last) {
      newNode.next = null;
     last = newNode;
   } else {
      newNode.next = current.next;

      current.next.previous = newNode;
    }
    newNode.previous = current;
    current.next = newNode;
    return true;
  }
public int count() {
if( head==null){
return 0;
}
Node node = head;
int count = 0;
while( true){
node = node.next;
if( node!=head){
count++;
}else{
break;
}
}
if( head==null){
System.out.println( " List is empty");
}else{
//Node node = head.previous.next;
    int i=1;
while(i <= count/2){
node = node.next;
i++;
if( node!=head){
System.out.print( node.item + " ");
}else{
break;
}
}
//System.out.println();
}
return count;
}

public int getLargest() {
//number below is the bottom negative range of integer
int largest = -2147483648;
if( head==null){
return largest;
}
Node node = head;
largest = head.item;
while( true){
node = node.next;
if( node!=head){
if( node.item > largest){
largest = node.item;
}
}else{
break;
}
}
return largest;
}

public void print(){
if( head==null){
System.out.println( " List is empty");
}else{
Node node = head.previous.next;
while( true){
node = node.next;
if( node!=head){
System.out.print( node.item + " ");
}else{
break;
}
}
System.out.println();
}
}


    
public static void main( String[] args){
DLinkedList list = new DLinkedList();
Random random = new Random();

//randomly add between 5 to 14 numbers to list
for(  int i=0; i< random.nextInt( 10)+5; i++){
//random insert numbers between 0 and 100, not including 100
list.Insert( random.nextInt( 100));
}

list.print();
System.out.println( "There are " + list.count() + " items in the list");
System.out.println( "The larget number in the list is " + list.getLargest());
list.insertAfter(random.nextInt(100), 77);

}
} 


i can found the middle of the list
but i cant insert new node

What errors? Where?

when i try to use the insertafter function

java.lang.NullPointerException
at DLinkedList.insertAfter(DLinkedList.java:37)
at DLinkedList.main(DLinkedList.java:148)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Nativ e Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(Unknow n Source)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(Un known Source)
at java.lang.reflect.Method.invoke(Unknown Source)
at edu.rice.cs.drjava.model.compiler.JavacCompiler.ru nCommand(JavacCompiler.java:271)
>

--- Update ---

PHP Code:

import java.util.Random;
 
public class DLinkedList {

private class Node {
int item;
Node next;
Node previous;

}

private Node head = null;


public void Insert(int item) {
if( head==null){
head = new Node();
head.item = item;
head.next = head;
head.previous = head;
}else{
Node newNode = new Node();
newNode.item = item;
Node tail = head.previous;
tail.next = newNode;
newNode.previous = tail;
newNode.next = head;
head.previous = newNode;
}
}


public boolean insertAfter(int key, int item) {
   Node first=null;
  Node last=null;
    Node current = first;
    while (current.item !=key) {
      current = current.next;
      if (current == null){
        return false;
      }
    }
   Node newNode = new Node();

    if (current == last) {
     newNode.next = null;
     last = newNode;
 } 
    else {
      newNode.next = current.next;

      current.next.previous = newNode;
    }
    newNode.previous = current;
    current.next = newNode;
    return true;
 }


public int count() {
if( head==null){
return 0;
}
Node node = head;
int count = 0;
while( true){
node = node.next;
if( node!=head){
count++;
}else{
break;
}
}
if( head==null){
System.out.println( " List is empty");
}else{
//Node node = head.previous.next;
    int i=1;
while(i <= count/2){
node = node.next;
i++;
if( node!=head){
System.out.print( node.item + " ");
}else{
break;
}
}
//System.out.println();
}
return count;
}



//public int getLargest() {
//number below is the bottom negative range of integer
//int largest = -2147483648;
//if( head==null){
//return largest;
//}
//Node node = head;
//largest = head.item;
//while( true){
//node = node.next;
//if( node!=head){
//if( node.item > largest){
//largest = node.item;
//}
//}else{
//break;
//}
//}
//return largest;
//}

public void print(){
if( head==null){
System.out.println( " List is empty");
}else{
Node node = head.previous.next;
while( true){
node = node.next;
if( node!=head){
System.out.print( node.item + " ");
}else{
break;
}
}
System.out.println();
}
}


    
public static void main( String[] args){
DLinkedList list = new DLinkedList();
Random random = new Random();

//randomly add between 5 to 14 numbers to list
for(  int i=0; i< random.nextInt( 10)+5; i++){
//random insert numbers between 0 and 100, not including 100
list.Insert( random.nextInt( 100));
}

list.print();
System.out.println( "`the middle of list at item no. " + list.count()/2 );
//System.out.println( "The larget number in the list is " + list.getLargest());
list.insertAfter(random.nextInt(100), 77);

}
} 


here is the code again

PHP Code:

[SIZE=4][LEFT]import java.util.Random;
 
public class DLinkedList {

private class Node {
int item;
Node next;
Node previous;

}

private Node head = null;


public void Insert(int item) {
if( head==null){
head = new Node();
head.item = item;
head.next = head;
head.previous = head;
}else{
Node newNode = new Node();
newNode.item = item;
Node tail = head.previous;
tail.next = newNode;
newNode.previous = tail;
newNode.next = head;
head.previous = newNode;
}
}


public boolean insertAfter(int key, int item) {
   Node first=null;
  Node last=null;
    Node current = first;
    while (current.item !=key) {
      current = current.next;
      if (current == null){
        return false;
      }
    }
   Node newNode = new Node();

    if (current == last) {
     newNode.next = null;
     last = newNode;
 } 
    else {
      newNode.next = current.next;

      current.next.previous = newNode;
    }
    newNode.previous = current;
    current.next = newNode;
    return true;
 }


public int count() {
if( head==null){
return 0;
}
Node node = head;
int count = 0;
while( true){
node = node.next;
if( node!=head){
count++;
}else{
break;
}
}
if( head==null){
System.out.println( " List is empty");
}else{
//Node node = head.previous.next;
    int i=1;
while(i <= count/2){
node = node.next;
i++;
if( node!=head){
System.out.print( node.item + " ");
}else{
break;
}
}
//System.out.println();
}
return count;
}



//public int getLargest() {
//number below is the bottom negative range of integer
//int largest = -2147483648;
//if( head==null){
//return largest;
//}
//Node node = head;
//largest = head.item;
//while( true){
//node = node.next;
//if( node!=head){
//if( node.item > largest){
//largest = node.item;
//}
//}else{
//break;
//}
//}
//return largest;
//}

public void print(){
if( head==null){
System.out.println( " List is empty");
}else{
Node node = head.previous.next;
while( true){
node = node.next;
if( node!=head){
System.out.print( node.item + " ");
}else{
break;
}
}
System.out.println();
}
}


    
public static void main( String[] args){
DLinkedList list = new DLinkedList();
Random random = new Random();

//randomly add between 5 to 14 numbers to list
for(  int i=0; i< random.nextInt( 10)+5; i++){
//random insert numbers between 0 and 100, not including 100
list.Insert( random.nextInt( 100));
}

list.print();
System.out.println( "`the middle of list at item no. " + list.count()/2 );
//System.out.println( "The larget number in the list is " + list.getLargest());
list.insertAfter(random.nextInt(100), 77);

}
}
[/LEFT][/SIZE] 


[SIZE=4][LEFT]import java.util.Random;
 
public class DLinkedList {
 
private class Node {
int item;
Node next;
Node previous;
 
}
 
private Node head = null;
 
 
public void Insert(int item) {
if( head==null){
head = new Node();
head.item = item;
head.next = head;
head.previous = head;
}else{
Node newNode = new Node();
newNode.item = item;
Node tail = head.previous;
tail.next = newNode;
newNode.previous = tail;
newNode.next = head;
head.previous = newNode;
}
}
 
 
public boolean insertAfter(int key, int item) {
   Node first=null;
  Node last=null;
    Node current = first;
    System.out.println( key);
    while (current.item !=key) {
 
      current = current.next;
      if (current == null){
        return false;
      }
    }
   Node newNode = new Node();
 
    if (current == last) {
     newNode.next = null;
     last = newNode;
 } 
    else {
      newNode.next = current.next;
 
      current.next.previous = newNode;
    }
    newNode.previous = current;
    current.next = newNode;
    return true;
 }
 
 
public int count() {
if( head==null){
return 0;
}
Node node = head;
int count = 0;
while( true){
node = node.next;
if( node!=head){
count++;
}else{
break;
}
}
if( head==null){
System.out.println( " List is empty");
}else{
//Node node = head.previous.next;
    int i=1;
while(i <= count/2){
node = node.next;
i++;
if( node!=head){
System.out.print( node.item + " ");
}else{
break;
}
}
//System.out.println();
}
return count;
}
 
 
 
//public int getLargest() {
//number below is the bottom negative range of integer
//int largest = -2147483648;
//if( head==null){
//return largest;
//}
//Node node = head;
//largest = head.item;
//while( true){
//node = node.next;
//if( node!=head){
//if( node.item > largest){
//largest = node.item;
//}
//}else{
//break;
//}
//}
//return largest;
//}
 
public void print(){
if( head==null){
System.out.println( " List is empty");
}else{
Node node = head.previous.next;
while( true){
node = node.next;
if( node!=head){
System.out.print( node.item + " ");
}else{
break;
}
}
System.out.println();
}
}
 
 
 
public static void main( String[] args){
DLinkedList list = new DLinkedList();
Random random = new Random();
 
//randomly add between 5 to 14 numbers to list
for(  int i=0; i< random.nextInt( 10)+5; i++){
//random insert numbers between 0 and 100, not including 100
list.Insert( random.nextInt( 100));
}
 
list.print();
System.out.println( "`the middle of list at item no. " + list.count()/2 );
//System.out.println( "The larget number in the list is " + list.getLargest());
list.insertAfter(random.nextInt(100), 77);
 
}
}
[/LEFT][/SIZE]

sorry for disturbance
i want to insert after the middle node

[SIZE=4][FONT=Microsoft Sans Serif][INDENT][INDENT]import java.util.Random;
 
public class DLinkedList {
 
private class Node {
int item;
Node next;
Node previous;
 
}
 
private Node head = null;
 
 
public void Insert(int item) {
if( head==null){
head = new Node();
head.item = item;
head.next = head;
head.previous = head;
}else{
Node newNode = new Node();
newNode.item = item;
Node tail = head.previous;
tail.next = newNode;
newNode.previous = tail;
newNode.next = head;
head.previous = newNode;
}
}
 
 
public boolean insertAfter(int key, int item) {
   Node first=null;
  Node last=null;
    Node current = first;
  //  System.out.println( key);
    while (current.item !=key) {
 
      current = current.next;
      if (current == null){
        return false;
      }
    }
   Node newNode = new Node();
 
    if (current == last) {
     newNode.next = null;
     last = newNode;
 } 
    else {
      newNode.next = current.next;
 
      current.next.previous = newNode;
    }
    newNode.previous = current;
    current.next = newNode;
    return true;
 }
 
 
public int count() {
if( head==null){
return 0;
}
Node node = head;
int count = 0;
while( true){
node = node.next;
if( node!=head){
count++;
}else{
break;
}
}
if( head==null){
System.out.println( " List is empty");
}else{
//Node node = head.previous.next;
    int i=1;
while(i <= count/2){
node = node.next;
i++;
if( node!=head){
System.out.print( node.item + " ");
}else{
break;
}
}
//System.out.println();
}
return count;
}
 
 
 
//public int getLargest() {
//number below is the bottom negative range of integer
//int largest = -2147483648;
//if( head==null){
//return largest;
//}
//Node node = head;
//largest = head.item;
//while( true){
//node = node.next;
//if( node!=head){
//if( node.item > largest){
//largest = node.item;
//}
//}else{
//break;
//}
//}
//return largest;
//}
 
public void print(){
if( head==null){
System.out.println( " List is empty");
}else{
Node node = head.previous.next;
while( true){
node = node.next;
if( node!=head){
System.out.print( node.item + " ");
}else{
break;
}
}
System.out.println();
}
}
 
 
 
public static void main( String[] args){
DLinkedList list = new DLinkedList();
//Random random = new Random();
 
//randomly add between 5 to 14 numbers to list
for(  int i=1; i<10; i++){
//random insert numbers between 0 and 100, not including 100
list.Insert(i);
}
 
list.print();
System.out.println( "`the middle of list after item no. " + list.count()/2 );
//System.out.println( "The larget number in the list is " + list.getLargest());
list.insertAfter(5, 77);
list.print();
}
}[/INDENT][/INDENT][/FONT][/SIZE]

import java.util.Random;

public class DLinkedList {

private class Node {
int item;
Node next;
Node previous;

}

private Node head = null;


public void Insert(int item) {
if( head==null){
head = new Node();
head.item = item;
head.next = head;
head.previous = head;
}else{
Node newNode = new Node();
newNode.item = item;
Node tail = head.previous;
tail.next = newNode;
newNode.previous = tail;
newNode.next = head;
head.previous = newNode;
}
}


public boolean insertAfter(int key, int item) {
Node first=null;
Node last=null;
Node current = first;
// System.out.println( key);
while (current.item !=key) {

current = current.next;
if (current == null){
return false;
}
}
Node newNode = new Node();

if (current == last) {
newNode.next = null;
last = newNode;
}
else {
newNode.next = current.next;

current.next.previous = newNode;
}
newNode.previous = current;
current.next = newNode;
return true;
}


public int count() {
if( head==null){
return 0;
}
Node node = head;
int count = 0;
while( true){
node = node.next;
if( node!=head){
count++;
}else{
break;
}
}
if( head==null){
System.out.println( " List is empty");
}else{
//Node node = head.previous.next;
int x=1;
while(x <= count/2){
node = node.next;
x++;
if( node!=head){
System.out.print( node.item + " ");
}else{
break;
}
}
//System.out.println();
}
return count;
}



//public int getLargest() {
//number below is the bottom negative range of integer
//int largest = -2147483648;
//if( head==null){
//return largest;
//}
//Node node = head;
//largest = head.item;
//while( true){
//node = node.next;
//if( node!=head){
//if( node.item > largest){
//largest = node.item;
//}
//}else{
//break;
//}
//}
//return largest;
//}

public void print(){
if( head==null){
System.out.println( " List is empty");
}else{
Node node = head.previous.next;
while( true){
node = node.next;
if( node!=head){
System.out.print( node.item + " ");
}else{
break;
}
}
System.out.println();
}
}



public static void main( String[] args){
DLinkedList list = new DLinkedList();
//Random random = new Random();

//randomly add between 5 to 14 numbers to list
for(int i=1; i<10; i++){
//random insert numbers between 0 and 100, not including 100
list.Insert(i);
}

list.print();
System.out.println( "`the middle of list after item no. " + list.count()/2 );
//System.out.println( "The larget number in the list is " + list.getLargest());
list.insertAfter(5, 77);
list.print();
}
}

--- Update ---

is it clear now??

what can i do??

[INDENT][INDENT][SIZE=5]import java.util.Random;
 
[INDENT][INDENT]public class DLinkedList {
 
private class Node {
int item;
Node next;
Node previous;
 
}[/INDENT][/INDENT]
 
private Node head = null;
 
 
[QUOTE][INDENT][INDENT]public void Insert(int item) {
if( head==null){
head = new Node();
head.item = item;
head.next = head;
head.previous = head;
}else{
Node newNode = new Node();
newNode.item = item;
Node tail = head.previous;
tail.next = newNode;
newNode.previous = tail;
newNode.next = head;
head.previous = newNode;
}
}
[/INDENT][/INDENT][/QUOTE]
[INDENT][INDENT][QUOTE]public boolean insertAfter(int key, int item) {
   Node first=null;
  Node last=null;
    Node current = first;
  //  System.out.println( key);
    while (current.item !=key) {
 
      current = current.next;
      if (current == null){
        return false;
      }
    }[/QUOTE][/INDENT][/INDENT]
   [INDENT][INDENT][QUOTE]Node newNode = new Node();
 
    if (current == last) {
     newNode.next = null;
     last = newNode;
 } 
    else {
      newNode.next = current.next;
 
      current.next.previous = newNode;
    }
    newNode.previous = current;
    current.next = newNode;
    return true;
 }
[/QUOTE][/INDENT][/INDENT]
 
[INDENT][INDENT][QUOTE]public int count() {
if( head==null){
return 0;
}
Node node = head;
int count = 0;
while( true){
node = node.next;
if( node!=head){
count++;
}else{
break;
}
}
if( head==null){
System.out.println( " List is empty");
}else{
//Node node = head.previous.next;
    int x=1;
while(x <= count/2){
node = node.next;
x++;
if( node!=head){
System.out.print( node.item + " ");
}else{
break;
}
}
//System.out.println();
}
return count;
}
 
[/QUOTE][/INDENT][/INDENT]
 
//public int getLargest() {
//number below is the bottom negative range of integer
//int largest = -2147483648;
//if( head==null){
//return largest;
//}
//Node node = head;
//largest = head.item;
//while( true){
//node = node.next;
//if( node!=head){
//if( node.item > largest){
//largest = node.item;
//}
//}else{
//break;
//}
//}
//return largest;
//}
 
[INDENT][INDENT][QUOTE]public void print(){
if( head==null){
System.out.println( " List is empty");
}else{
Node node = head.previous.next;
while( true){
node = node.next;
if( node!=head){
System.out.print( node.item + " ");
}else{
break;
}
}
System.out.println();
}
}
 
 
 
public static void main( String[] args){
DLinkedList list = new DLinkedList();
//Random random = new Random();
 
//randomly add between 5 to 14 numbers to list
for(int i=1; i<10; i++){
//random insert numbers between 0 and 100, not including 100
list.Insert(i);
}
 
list.print();
System.out.println( "`the middle of list after item no. " + list.count()/2 );
//System.out.println( "The larget number in the list is " + list.getLargest());
list.insertAfter(5, 77);
list.print();
}
}[/QUOTE][/INDENT][/INDENT]
[/SIZE][/INDENT][/INDENT]

--- Update ---

are there any another method to put my code??

--- Update ---

[INDENT][INDENT]import java.util.Random;
 
public class DLinkedList {
 
private class Node {
int item;
Node next;
Node previous;
 
}
 
private Node head = null;
 
 
public void Insert(int item) {
if( head==null){
head = new Node();
head.item = item;
head.next = head;
head.previous = head;
}else{
Node newNode = new Node();
newNode.item = item;
Node tail = head.previous;
tail.next = newNode;
newNode.previous = tail;
newNode.next = head;
head.previous = newNode;
}
}
 
 
public boolean insertAfter(int key, int item) {
   Node first=null;
  Node last=null;
    Node current = first;
  //  System.out.println( key);
    while (current.item !=key) {
 
      current = current.next;
      if (current == null){
        return false;
      }
    }
   Node newNode = new Node();
 
    if (current == last) {
     newNode.next = null;
     last = newNode;
 } 
    else {
      newNode.next = current.next;
 
      current.next.previous = newNode;
    }
    newNode.previous = current;
    current.next = newNode;
    return true;
 }
 
 
public int count() {
if( head==null){
return 0;
}
Node node = head;
int count = 0;
while( true){
node = node.next;
if( node!=head){
count++;
}else{
break;
}
}
if( head==null){
System.out.println( " List is empty");
}else{
//Node node = head.previous.next;
    int x=1;
while(x <= count/2){
node = node.next;
x++;
if( node!=head){
System.out.print( node.item + " ");
}else{
break;
}
}
//System.out.println();
}
return count;
}
 
 
 
//public int getLargest() {
//number below is the bottom negative range of integer
//int largest = -2147483648;
//if( head==null){
//return largest;
//}
//Node node = head;
//largest = head.item;
//while( true){
//node = node.next;
//if( node!=head){
//if( node.item > largest){
//largest = node.item;
//}
//}else{
//break;
//}
//}
//return largest;
//}
 
public void print(){
if( head==null){
System.out.println( " List is empty");
}else{
Node node = head.previous.next;
while( true){
node = node.next;
if( node!=head){
System.out.print( node.item + " ");
}else{
break;
}
}
System.out.println();
}
}
 
 
 
public static void main( String[] args){
DLinkedList list = new DLinkedList();
//Random random = new Random();
 
//randomly add between 5 to 14 numbers to list
for(int i=1; i<10; i++){
//random insert numbers between 0 and 100, not including 100
list.Insert(i);
}
 
list.print();
System.out.println( "`the middle of list after item no. " + list.count()/2 );
//System.out.println( "The larget number in the list is " + list.getLargest());
list.insertAfter(5, 77);
list.print();
}
}[/INDENT][/INDENT]

--- Update ---

ah..is it clear now??
i'm so tired..

[INDENT][INDENT][INDENT]import java.util.Random;
 
public class DLinkedList {
 
private class Node {
int item;
Node next;
Node previous;
 
}
 
private Node head = null;
 
 
public void Insert(int item) {
if( head==null){
head = new Node();
head.item = item;
head.next = head;
head.previous = head;
}else{
Node newNode = new Node();
newNode.item = item;
Node tail = head.previous;
tail.next = newNode;
newNode.previous = tail;
newNode.next = head;
head.previous = newNode;
}
}
 
 
public boolean insertAfter(int key, int item) {
   Node first=null;
  Node last=null;
    Node current = first;
  //  System.out.println( key);
    while (current.item !=key) {
 
      current = current.next;
      if (current == null){
        return false;
      }
    }
   Node newNode = new Node();
 
    if (current == last) {
     newNode.next = null;
     last = newNode;
 } 
    else {
      newNode.next = current.next;
 
      current.next.previous = newNode;
    }
    newNode.previous = current;
    current.next = newNode;
    return true;
 }
 
 
public int count() {
if( head==null){
return 0;
}
Node node = head;
int count = 0;
while( true){
node = node.next;
if( node!=head){
count++;
}else{
break;
}
}
if( head==null){
System.out.println( " List is empty");
}else{
//Node node = head.previous.next;
    int x=1;
while(x <= count/2){
node = node.next;
x++;
if( node!=head){
System.out.print( node.item + " ");
}else{
break;
}
}
//System.out.println();
}
return count;
}
 
 
 
//public int getLargest() {
//number below is the bottom negative range of integer
//int largest = -2147483648;
//if( head==null){
//return largest;
//}
//Node node = head;
//largest = head.item;
//while( true){
//node = node.next;
//if( node!=head){
//if( node.item > largest){
//largest = node.item;
//}
//}else{
//break;
//}
//}
//return largest;
//}
 
public void print(){
if( head==null){
System.out.println( " List is empty");
}else{
Node node = head.previous.next;
while( true){
node = node.next;
if( node!=head){
System.out.print( node.item + " ");
}else{
break;
}
}
System.out.println();
}
}
 
 
 
public static void main( String[] args){
DLinkedList list = new DLinkedList();
//Random random = new Random();
 
//randomly add between 5 to 14 numbers to list
for(int i=1; i<10; i++){
//random insert numbers between 0 and 100, not including 100
list.Insert(i);
}
 
list.print();
System.out.println( "the middle of list after item no. " + list.count()/2 );
//System.out.println( "The larget number in the list is " + list.getLargest());
list.insertAfter(5, 77);
list.print();
}
}[/INDENT][/INDENT][/INDENT]

i changed all the font and formatting in my IDE

can i make it as attachment file