Question

In this Java program you will implement your own doubly linked lists.
Implement the following operations that Java7 LinkedLists have.

1. public DList()
This creates the empty list

2. public void addFirst(String element)
adds the element to the front of the list

3. public void addLast(String element)
adds the element to the end of the list

4. public String getFirst()

5. public String getLast()

6. public String removeLast()
removes & returns the last element of the list.

7. public String removeFirst()
removes & returns the front element of the list.

8. public String get(int index)
Returns the value at “position” index. IndexOutOfBoundsException should be
thrown if the index is non-existent.

9. public String set(int index, String value)
changes the value at “position” index and returns the old value. IndexOutOfBoundsException should be thrown if the index is non-existent.

10. public int indexOf(Object obj)
Returns the index of obj if it is in the list and -1 otherwise.

11. public int size()

12.public boolean contains(Object obj)
Returns true if obj appears in the list and false otherwise.

13. public Iterator iterator()
Returns an iterator over the list. This should be a non static inner class.

Answer 1

Hi,

Doubly linked list implementation code is given below:

public class DoublyLinkedListImpl {

private Node head ;

private Node tail ;

private int size ;

public DoublyLinkedListImpl () {

size = 0;

}

private class node{

E element;

Node next;

Node prev;

public Node(E element,Node next,Node prev){

this.element=element;

this.next=next;

this.prev=prev;

}

}

/** creates an empty list

public Dlist () {

size=0;

head = new DNode ( null,null,null); //create head

tail = new DNode ( null,head,null) // create tail

// make head and tail point to each other

head.setnext(tail);

}

public void addFirst (E element) {

Node tmp = new Node (element , head ,null);

if (head ! = null)

{

head.prev = tmp;

}

head = tmp;

if(tail == null)

{

tail = tmp;

}

size++;

System.out.println("adding:" +element);

}

public void addLast(E element) {

Node tmp = new Node(element,null,tail);

if(tail != null)

{

tail.next=tmp;

}

tail=tmp;

if(head == null)

{

head=tmp;

}

size++;

System.out.prrintln("adding:" +element);

}

public String getFirst(E element) {

final node<E> f= first;

if(f=null)

throw new noSuchElementException();

return f.item;

}

public String getLast(E element) {

final Node<E> l=last;

if(l==null)

throw new noSuchElementException();

return l.item;

}

public String removeFirst() {

if(size == 0) throw new NoSuchElementException();

Nodetmp = head;

head = head.next;

head.prev=null;

size --;

System.out.println("deleted:"+tmp.element);

return tmp.element;

}

public String removeLast() {

if(size == 0) throw new NoSuchElementException();

Node tmp = tail;

tail=tail.prev;

tail.next=null;

size--;

System.out.println("deleted:" +tmp.element);

return tmp.element;

}

public String get(int index) {
int i=0; cn;

if(index == 0) ;throw new IndexOutOfBoundsException();

for(Node *cn = head; cn != Null; cn-> nextnode) {

if(i == index){

return (cn -> value);

}

else {

return -1;

}

}

public String set(int index,E element){

checkElementIndex(index); throw new IndexOutOfBoundsException();

Node <E> x = node(index);

E oldVal = x.item;

x.item = element;

return oldVal;

}

public int indexof(Object o) {

int index = 0;

if(o== null){

for(Node<E> x = first; x!= null; x=x.next){

if(x.item == null)

return index;

index ++;

}

}else {

for (Node<E> x=first;x!= null;x=x.next) {

if(o.equals(x.item))

return index;

index++;

}

}

return -1;

}

public int size () {

return size;

}

public boolean contains (object o){

return indexOf(o)!=-1;

}

public iterator <E> iterator() {

return new iterator();

}

Hope you help this ...

Thank you..