Linked Lists In this assignment you will write a program that implements a varia

Question

Linked Lists In this assignment you will write a program that implements a variant of a linked list. This variant has a dummy node pointed to by the head link as shown in the following figure: Linked list with a dummy first node: item next tem next item next head -3 17 size2 This trick will allow your code to be a little simpler, not requiring a special case for add or remove operations at index 0. Your constructor method will be: public LinkedList(i head- new Node(null); size 0; You need to write a class called LinkedList that implements the following List interface // a list interface public interface List public boolean isEmptyl); // returns true if the list is empty, false otherwise

Explanation / Answer

import java.util.Collection; import java.util.Iterator; import java.util.List; import java.util.ListIterator; public class LinkedList implements List { int size ; /** *Creates a Inner class Node which represents an actual Node of a list */ class Node{ int item; Node next = null; public Node(){ } public Node(int item) { this.item = item; } } private Node head ; private Node last; /** * */ public LinkedList(){ head = new Node(); this.size = 0 ; } /** *Returns size of linked list * @return */ @Override public int size() { return this.size; } public boolean add(int item) { Node node = new Node(item); last.next = node; last = last.next; this.size++; return node == last; } /** *Element is added at last * @param o * @return */ @Override public boolean add(Object o) { if (o instanceof Node){ Node node = (Node)o; last.next = node; last = last.next; this.size++; return node == last; } return false; } /** *Element is added at given index * @param index * @param o */ @Override public void add(int index, Object o) { if(! (o instanceof Node)) return; Node temp = head.next; //if index = 0 code will make head point to new node while(index >0){ temp = temp.next; index--; } Node node = (Node)o; node.next = temp.next; temp.next = node; } /** * Removes object at index and returns the object . Else Null is returned * @param index * @return */ @Override public Object remove(int index) { if( index > this.size) return null; Node temp = head.next; Node node = null; //at index =0 code makes head point to 1st Index node while(index >0 && temp!=null ){ temp = temp.next; index--; } node = temp.next; temp.next = node.next; this.size--; return node; } /** * if Element is not found returns false else removes element and returns true * @param o * @return */ @Override public boolean remove(Object o) { if(! ( o instanceof Node)) return false; boolean elementFound = false; Node temp = head.next; Node node = (Node)o; //at index =0 code makes head point to 1st Index node while(temp.next!= null ){ if (temp.next == node) { elementFound = true;break; } temp = temp.next; } if(elementFound) { temp.next = node.next; this.size--; } return elementFound; } /** * Returns duplicate List * @return */ public List duplicate(){ LinkedList duplicateHead = new LinkedList(); Node temp = this.head.next; while(temp != last){ duplicateHead.add(temp.item); } return duplicateHead; } /** *Returns reverse duplicated LinkedList * @return */ public List duplicateReversed(){ LinkedList duplicateReversedHead = (LinkedList) duplicate(); Object [] array = duplicateReversedHead.toArray(); for(int index =array.length-1;index>=0;index-- ){ duplicateReversedHead.add((Node)array[index]); } return duplicateReversedHead; } /** * Converts Linked List to Object Array * @return */ @Override public Object[] toArray() { Object[] array = new Object[this.size]; Node tempNode = head.next; int index = 0; while(tempNode != last){ array[index++] = tempNode; } return array; } @Override public boolean contains(Object o) { return false; } @Override public Iterator iterator() { return null; } @Override public Object[] toArray(Object[] objects) { return new Object[0]; } /** *is size is 0 returns true * @return */ @Override public boolean isEmpty() { return this.size == 0; } @Override public boolean containsAll(Collection collection) { return false; } @Override public boolean addAll(Collection collection) { return false; } @Override public boolean addAll(int i, Collection collection) { return false; } @Override public boolean removeAll(Collection collection) { return false; } @Override public boolean retainAll(Collection collection) { return false; } @Override public void clear() { } @Override public Object get(int i) { return null; } @Override public Object set(int i, Object o) { return null; } @Override public int indexOf(Object o) { return 0; } @Override public int lastIndexOf(Object o) { return 0; } @Override public ListIterator listIterator() { return null; } @Override public ListIterator listIterator(int i) { return null; } @Override public List subList(int i, int i1) { return null; } }

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.