Generic Linked List

Need help creating a method to insert a value anywhere in a linked lis

Page 1 of 1

3 Replies - 18532 Views - Last Post: 29 October 2009 - 05:24 PM Rate Topic: -----

#1 lorigami  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 28-October 09

Generic Linked List

Posted 28 October 2009 - 06:31 PM

So, for the assignment we are supposed to create a generic linked list. I have most of it but having trouble creating an add method that can insert a value anywhere in the linked list.

public class LinkedList<Type> {

/** The first node in the list; represents the entire list.
* All nodes in the list can be accessed starting from head.
* The pointer is null if the list is empty. */
protected Node<Type> head = null;
/** The number of nodes in the list. Must always be > 0. */
protected int size = 0;

/* Note: we don't need a constructor as fields are initialized.

/** Returns the size of the list.
* @return number of nodes in the list */
public int size () {
return size;
}

/** Appends a value (within a node) at the end of the list.
* Recursive implementation.
* @param value to store at the tail of the list */
public void add (Type value) {
if (head == null) { // list is empty
head = new Node<Type> (value, null);
} else { // begin recursive add
add (head, value);
}
size++;
}

/** Appends a value (within a node) at the end of the sublist.
* @param node head of the sublist
* @param value to append to the end of the sublist */
private Node<Type> add (Node<Type> node, Type value) {
if (node.next () == null) { // base case: node is the last in list
node.setNext (new Node<Type> (value, null));
} else { // recurse with a shorter sublist of next node
add (node.next (), value);
}
return node;
}

/** Appends a value (within a node) at the end of the list.
* Iterative implementation.
* @param node head of the sublist
* @param value to append to the end of the sublist */
public void add2 (Type value) {
if (head == null) { // list is empty
head = new Node<Type> (value, null);
} else {
Node<Type> current = head; // guaranteed not to be null initially
Node<Type> next = current.next ();
while (next != null) {
current = next; // guaranteed not to be null
next = current.next ();
}
// now, next is guaranteed to be null
// current is not null, i.e. it's the last node
current.setNext (new Node<Type> (value, null));
}
size++;
}

// /** Appends a value (withn a node) at a given index in the list.
// *Iterative implementation
// * @param node head of the sublist
// * @param value to append to a given index in the sublist */
// public void addAtIndex(Type value){
// if(head == null){
// head = new Node<Type> (value, null);
// }else{
//
// }
// }
//


/** Removes the item at index from the list.
* @param index of item to be removed
* @throws NodeCountException if this is not a valid position
* position is 1-based, so position = 1 removes the head */
public void remove (int index) throws NodeCountException {
if ((index < 1) || (index > size)) {
throw new NodeCountException ("invalid index " + index
+ ": only 1.." + size + " items are available");
}
if (index == 1) { // remove 1st node
head = head.next (); // now, list starts with node that was the 2nd
// and the previously 1st node is unreachable
} else {
Node<Type> node = head;
for (int i = 2; i < index; i++) {
node = node.next ();
}
// set node's next to refer to the node after the next
node.setNext (node.next ().next ());
// now the previously index-th node is unreachable
}
// the unreachable node will be eventually garbage collected
size--; // one less item
}

/** Converts the list to a printable string.
* @return text representing all the nodes in the list */
public String toString () {
return toString (head);
}

/** Converts the sublist that starts at node to a printable string.
* @return text representing all the nodes in the list */
private String toString (Node<Type> node) {
if (node == null) { // base case: no nodes in the list
return "";
} else { // convert node to text and recurse with remainder list
Node<Type> next = node.next ();
return node.value () + (next == null ? "" : "\n") + toString (next);
}
}

Is This A Good Question/Topic? 0
  • +

Replies To: Generic Linked List

#2 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8378
  • View blog
  • Posts: 31,956
  • Joined: 06-March 08

Re: Generic Linked List

Posted 28 October 2009 - 08:50 PM

Please :code:
reading unindented code is a nightmare and it is rule #4 of this forum

And while you are at it also post your Node class code
Was This Post Helpful? 0
  • +
  • -

#3 lorigami  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 28-October 09

Re: Generic Linked List

Posted 29 October 2009 - 04:09 PM

Here is my linked list
public class LinkedList<Type> {

 /** The first node in the list; represents the entire list.
   * All nodes in the list can be accessed starting from head.
   * The pointer is null if the list is empty. */
 protected Node<Type> head = null;
 /** The number of nodes in the list. Must always be > 0. */
 protected int size = 0;
 
 /* Note: we don't need a constructor as fields are initialized.

 /** Returns the size of the list.
   * @return number of nodes in the list */
 public int size () {
   return size;
 }

 /** Appends a value (within a node) at the end of the list.
   * Recursive implementation.
   * @param value to store at the tail of the list */
 public void add (Type value) {
   if (head == null) { // list is empty
	 head = new Node<Type> (value, null);
   } else { // begin recursive add
	 add (head, value);
   }
   size++;
 }

 /** Appends a value (within a node) at the end of the sublist.
   * @param node head of the sublist
   * @param value to append to the end of the sublist */
 private Node<Type> add (Node<Type> node, Type value) {
   if (node.next () == null) { // base case: node is the last in list
	 node.setNext (new Node<Type> (value, null));
   } else { // recurse with a shorter sublist of next node
	 add (node.next (), value);
   }
   return node;
 }

 /** Appends a value (within a node) at the end of the list.
   * Iterative implementation.
   * @param node head of the sublist
   * @param value to append to the end of the sublist */
 public void add2 (Type value) {
   if (head == null) { // list is empty
	 head = new Node<Type> (value, null);
   } else {
	 Node<Type> current = head; // guaranteed not to be null initially
	 Node<Type> next = current.next ();
	 while (next != null) {
	   current = next; // guaranteed not to be null
	   next = current.next (); 
	 }
	 // now, next is guaranteed to be null
	 // current is not null, i.e. it's the last node
	 current.setNext (new Node<Type> (value, null));
   }
   size++;
 }
 
// /** Appends a value (withn a node) at a given index in the list.
//  *Iterative implementation
//  * @param node head of the sublist
//  * @param value to append to a given index in the sublist */
// public void addAtIndex(Type value){
//	 if(head == null){
//		 head = new Node<Type> (value, null); 
//	 }else{
//		 
//	 }
// }
// 


 /** Removes the item at index from the list.
   * @param index of item to be removed
   * @throws NodeCountException if this is not a valid position
   *	 position is 1-based, so position = 1 removes the head */
 public void remove (int index) throws NodeCountException {
   if ((index < 1) || (index > size)) {
	 throw new NodeCountException ("invalid index " + index
		 + ": only 1.." + size + " items are available");
   }
   if (index == 1) { // remove 1st node 
	 head = head.next (); // now, list starts with node that was the 2nd
						  // and the previously 1st node is unreachable
   } else {
	 Node<Type> node = head;
	 for (int i = 2; i < index; i++) {
	   node = node.next ();
	 }
	 // set node's next to refer to the node after the next
	 node.setNext (node.next ().next ());
	 // now the previously index-th node is unreachable
   }
   // the unreachable node will be eventually garbage collected
   size--;	  // one less item
 }

 /** Converts the list to a printable string.
   * @return text representing all the nodes in the list */
 public String toString () {
   return toString (head);
 }

 /** Converts the sublist that starts at node to a printable string.
   * @return text representing all the nodes in the list */
 private String toString (Node<Type> node) {
   if (node == null) { // base case: no nodes in the list
	 return "";
   } else { // convert node to text and recurse with remainder list
	 Node<Type> next = node.next ();
	 return node.value () + (next == null ? "" : "\n") + toString (next);
   }
 }



And here is my node class

public class Node<Type> {
  /* The link to the next node in the linked list.
   * If there is no next node, the pointer is null. */
  private Type value;
  /** The data object that this node contains. */
  private Node<Type> next;

  /** Creates a new Node.
	* @param value the data objects within the node
	* @param next the next node in the linked list */
  public Node (Type value, Node<Type> next) {
	this.value = value;
	this.next = next;
  }

  /* accessor methods */
  
  /** Returns the data contained in this Node.
	* @return the object within this Node */
  public Type value () {
	return value;
  }

  /** Returns the next node in the linked list.
	* @return reference to the next Node */
  public Node<Type> next () {
	return next;
  }

  /* mutator methods */

  /** Sets the data that this Node should hold.
	* @param the object this Node should store */
  public void setValue(Type value) {
	this.value = value;
  }

  /** Sets the next node in the linked list.
	* @param reference to the next Node */
  public void setNext (Node<Type> next) {
	this.next = next;
  }
}




Was This Post Helpful? 0
  • +
  • -

#4 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8378
  • View blog
  • Posts: 31,956
  • Joined: 06-March 08

Re: Generic Linked List

Posted 29 October 2009 - 05:24 PM

Some thing like ?

public void addAtIndex(int index, Type value){
	 if(index > size)
		 throw exception....
	 Node node = head;
	 for(int i = 1; i < index; i++)
		  node = node.next();
	 Node savedNext = node.next();
	 node.next = new Node(value);
	 node.next.next = savedNext();
}



node
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1