#include <stdio.h>
typedef char DATA;
struct linked_list {
DATA   d;
struct linked_list   *next;
};
typedef struct linked_list ELEMENT;
typedef ELEMENT *   LINK;

struct data{
char name[10];
int age;
int weight;
}
typedef struct data DATA;

import java.util.NoSuchElementException;

// doubly-linked list
// where Node is a nested class, which now also has a backward reference,
// this implementation has a head and a tail.

public class LinkedList extends Object {

    // nested-class

    private static class Node {

	private Object value;

	private Node previous; // <-- NEW
	private Node next;

	Node (Object value, Node previous, Node next) {  // <-- CHANGED
	    this.value = value;
	    this.previous = previous;
	    this.next = next;
	}
    }

    // Instance variables

    private Node head;
    private Node tail;

    // Representation of the empty list.

    public LinkedList () {
        head = null;
	tail = null;
    }

    // IDEM

    public int size() {
	Node p = head;
	int count = 0;
	while (p!=null) {
	    p = p.next;
	    count++;
	}
	return count;
    }

    public void addFirst(Object o) {

	if (o == null)
	    throw new IllegalArgumentException("null");

	head = new Node(o, null, head); // has no previous!

	if (tail == null)
	    tail = head;
	else
	    head.next.previous = head; // all the elements must be connected
	                               // to their predecessor (memory diagram?)
    }

    public void addLast(Object o) {

	if (o == null)
	    throw new IllegalArgumentException("null");

	if (head == null) {

	    head = new Node(o, null, null);
	    tail = head;

	} else {

	    tail.next = new Node(o, tail, null); // draw the memory diagram for this
	    tail = tail.next;

	}
    }

    // IDEM

    public Object get(int pos) {

	if (pos < 0) 
	    throw new IndexOutOfBoundsException(Integer.toString(pos));

	Node p = head;
	
	for (int i=0; i<pos; i++)
	    if (p == null)
		throw new IndexOutOfBoundsException(Integer.toString(pos));
	    else
		p = p.next;

	return p.value;
    }

    public void add(int pos, Object o) {

	if (o == null)
	    throw new IllegalArgumentException("null");

	if (pos < 0) 
	    throw new IndexOutOfBoundsException(Integer.toString(pos));

	if (pos == 0) {
	    head = new Node (o, null, head);
	    if (tail == null)
		tail = head;
	    else
		head.next.previous = head; // memory diagram
	} else {

	    Node p = head;
	    
	    for (int i = 0; i < (pos-1); i++)
		if (p == null)
		    throw new IndexOutOfBoundsException(Integer.toString(pos));
		else
		    p = p.next;
	    
	    p.next = new Node (o, p, p.next);

	    if (p == tail)
		tail = p.next;
            else
		p.next.next.previous = p.next;
	}
    }

    public boolean remove(Object o) {

	if (head == null)
	    return false;
	
	// having previous pointers opens up avenues for
	// other strategies

	Node p = head;

	while (p != null && ! p.value.equals(o))
		p = p.next;

	if (p == null) // o was not found
	    return false;

	if (p == head) { // o occurs at position 0

	    head = head.next;

	    if (head == null)
		tail = null; // this was the last element
	    else
		head.previous = null;

	    p.value = null;
	    p.next = null;

	} else {

	    Node nodeToDelete = p;

	    p = p.previous; // moving backwards

	    p.next = nodeToDelete.next;

	    if (nodeToDelete == tail)
		tail = p;
	    else
		p.next.previous = p;

	    nodeToDelete.value = null;
	    nodeToDelete.next = null;

	}

	return true;
    }

    public Object removeFirst() {

	if (head == null)
	    throw new NoSuchElementException();
	
	Node toDelete = head;
  	Object savedValue = head.value;

      	head = head.next;

	if (head == null)
	    tail = null;
	else
	    head.previous = null; // <-- !!!
    
	toDelete.next = null;
	toDelete.value = null;

  	return savedValue;
    }

    public Object removeLast() {

	if (head == null)
	    throw new NoSuchElementException();
	
	// Ok, we now have at least one element

        Node toDelete;

        if (head.next == null) {

            toDelete = head;
            head = null;
            tail = null;

        } else {

	    // no traversal involved

            toDelete = tail;

            tail = tail.previous;
	    tail.next = null;
        }

        Object savedValue;
	savedValue = toDelete.value;

	toDelete.value = null;
        toDelete.next = null;

        return savedValue;
    }
}