Hello Friends
I have This important question about implementing double link list I have done it but it dosenot work , please try to find what is wrong..
Thank you but I need this work queckly...
CLASS LINK LIST:-
public class LinkList {
[I][/I]
public class LinkedList<T> {
private DoubleLinkList<T> head;
/* default constructor...
*/
public LinkedList() {
}
;
////////////////////////////////////////////////////////////////////////////
public boolean isEmpty() {
return head == null;
}
////////////////////////////////////////////////////////////////////////////
public void addFirst(T elem) {
DoubleLinkList<T> node = new DoubleLinkList<T>(elem);
node.setNext(head);
head = node;
}
////////////////////////////////////////////////////////////////////////////
public void addLast(T elem) {
DoubleLinkList<T> node = new DoubleLinkList<T>(elem);
if (head == null) {
head = node;
} else {
DoubleLinkList<T> h = head;
for (; h.getNext() != null; h = h.getNext());
h.setNext(node);
}
}
////////////////////////////////////////////////////////////////////////////
/**
*
* @param elem to be added at the end of the list
* @return true if element was added, false otherwise
*/
public boolean add(T elem) {
addLast(elem);
return true;
}
////////////////////////////////////////////////////////////////////////////
/**
* adding an object at specific index of the linked list.
* @param index
* @param elem
*/
public void add(int index, T elem) {
//java.util.LinkedList<T> lst;
//lst.re
int _index = index;
int N = size();
DoubleLinkList<T> h = head;
DoubleLinkList<T> prev = null;
for (; index > 0 && h != null; index--, prev = h, h = h.getNext());
if (index != 0) {
throw new RuntimeException("Index:" + _index + " outOfBound add(int,T), size:" + N);
}
DoubleLinkList<T> node = new DoubleLinkList<T>(elem);
node.setNext(h);
if (prev != null) {
prev.setNext(node);
} else {
head = node;
}
}
////////////////////////////////////////////////////////////////////////////
public int size() {
DoubleLinkList<T> h = head;
int count = 0;
while (h != null) {
h = h.getNext();
count++;
}
return count;
}
////////////////////////////////////////////////////////////////////////////
public String toString() {
String str = "[";
DoubleLinkList<T> h = head;
while (h != null) {
str += h.getData() + "-->";
h = h.getNext();
}
str += " ]";
return str;
}
////////////////////////////////////////////////////////////////////////////
public T removeFirst() {
if (head == null) {
return null;
}
DoubleLinkList<T> first = head;
head = head.getNext();
return first.getData();
}
////////////////////////////////////////////////////////////////////////////
public T remove() {
return removeFirst();
}
////////////////////////////////////////////////////////////////////////////
public T removeLast() {
if (head == null) {
return null;
} else {
DoubleLinkList<T> current = head;
DoubleLinkList<T> prev = null;
for (; current.getNext() != null; current = current.getNext()) {
prev = current;
}
T data = current.getData();
if (prev == null) {
head = null;
} else {
prev.setNext(null);
}
return data;
}
}
////////////////////////////////////////////////////////////////////////////
/**
* remove element/object at specific index in the linked list
* @param index
* @return
*/
public T remove(int index) {
//java.util.LinkedList<T> lst;
//lst.re
int _index = index;
int N = size();
DoubleLinkList<T> h = head;
DoubleLinkList<T> prev = null;
for (; index > 0 && h != null; index--, prev = h, h = h.getNext());
if (index != 0 || h == null) {
throw new RuntimeException("Index:" + _index + " outOfBound remove(int), size:" + N);
}
T data = h.getData();
if (prev != null) {
prev.setNext(h.getNext());
} else {
head = head.getNext();
}
return data;
}
////////////////////////////////////////////////////////////////////////////
/**
* remove the first occurance of specific object in the linked list.
* @param data
* @return
*/
public boolean remove(Object data) {
//java.util.LinkedList<T> lst;
//lst.cl
DoubleLinkList<T> h = head;
DoubleLinkList<T> prev = null;
for (; h != null; prev = h, h = h.getNext()) {
if (h.getData().equals(data)) {
if (prev != null) {
prev.setNext(h.getNext());
} else {
head = head.getNext();
}
return true;
}
}
return false;
}
////////////////////////////////////////////////////////////////////////////
/**
* sort the linked list using selection sort.
*/
public void sort() {
int count;
while (true) {
DoubleLinkList<T> prev = null;
count = 0;
for (DoubleLinkList<T> curr = head; curr != null && curr.getNext() != null;) {
Comparable c = (Comparable) curr.getData();
if (c.compareTo(curr.getNext().getData()) > 0) {
//swap curr and curr.next
// -->prev-->curr-->next-->...
// --> prev-->next-->curr-->...
DoubleLinkList<T> next = curr.getNext();
curr.setNext(next.getNext());
next.setNext(curr);
if (prev != null) {
prev.setNext(next);
} else {
head = next;
}
prev = next;
count++;
} else {
prev = curr;
curr = curr.getNext();
}
}
if (count == 0) {
break;
}
}
}
////////////////////////////////////////////////////////////////////////////
/**
* check if the linked list is sorted or not.
* @return
*/
public boolean isSorted() {
int N = size();
if (N <= 1) {
return true;
}
DoubleLinkList<T> curr = head;
while (curr.getNext() != null) {
Comparable cData = (Comparable) curr.getData();
Comparable nData = (Comparable) curr.getNext().getData();
if (cData.compareTo(nData) > 0) {
return false;
}
curr = curr.getNext();
}
return true;
}
////////////////////////////////////////////////////////////////////////////
/**
* clear/delete all elements in the linked list.
*/
public void clear() {
DoubleLinkList<T> prev = null;
while (head != null) {
prev = head;
head = head.getNext();
prev.setNext(null);
}
}
////////////////////////////////////////////////////////////////////////////
public T get(int index) {
DoubleLinkList<T> h = head;
int N = size();
for (int i = 0; i < N; i++) {
if (i == index) {
return h.getData();
} else {
h = h.getNext();
}
}
throw new RuntimeException("index out of bound exception");
}
////////////////////////////////////////////////////////////////////////////
/**
* reverse the linked list.
*/
public void reverse() {
if (size() <= 1) {
return;
}
DoubleLinkList<T> h = head;
DoubleLinkList<T> prev = null;
while (h != null) {
DoubleLinkList<T> next = h.getNext();
h.setNext(prev);
prev = h;
h = next;
}
head = prev;
}
/**
* another way of reversing the linked list.
*/
public void reverse1() {
LinkedList<T> lst = new LinkedList<T>();
DoubleLinkList<T> h = head;
for (; h != null; h = h.getNext()) {
T data = this.removeFirst();
lst.addFirst(data);
}
this.head = lst.head;
}
////////////////////////////////////////////////////////////////////////////
}
}double link list class
public class DoubleLinkList<T> {
protected T data;
protected DoubleLinkList<T> Next;
private DoubleLinkList<T> prev;
public DoubleLinkList(T data) {
this.data = data;
}
public T getData() {
return data;
}
public void setNext(DoubleLinkList<T> next) {
this.Next = next;
}
public void setPrev(DoubleLinkList<T> prev) {
this.prev = prev;
}
public DoubleLinkList<T> getNext() {
return Next;
}
public DoubleLinkList<T> getPrev() {
return prev;
}
public boolean isEmpty() {
return Next == null;
}
//to add item to the list and they added in the firt of the list
public void addFirst(T element) {
DoubleLinkList<T> node = new DoubleLinkList<T>(element);
if (isEmpty()) {
Next= node;
} else {
node.setNext(Next);
Next = node;
}
}
//to add item to the last of the list
public void addLast(T data) {
DoubleLinkList<T> newNode = new DoubleLinkList<T>(data); //step1
if (Next == null) {
Next = newNode; // list is empty
} else {
DoubleLinkList<T> h = Next; //step2
for (; h.getNext() != null; h = h.getNext()); //step3
h.setNext(newNode); //step4
}
}
public boolean addAfter(T key, long dd) {
DoubleLinkList curr = prev;
while (curr.getData()!= key){
curr = curr.Next;
if (curr == null)
return false; // cannot find it
}
DoubleLinkList newLink = new DoubleLinkList(dd); // make new link
if (curr == Next) // if last link,
{
newLink.Next = null;
Next = newLink;
} else // not last link,
{
newLink.Next = curr.Next;
curr.Next.prev = newLink;
}
newLink.prev = curr;
curr.Next = newLink;
return true; // found it, insert
}
//to print the list
public String Print() {
String str = "[";
DoubleLinkList<T> h = Next;
while (h != null) {
str = h.getData() + "->";
h = h.getNext();
}
str += "]";
return str;
}
//to get how many node in the list
public int size() {
DoubleLinkList<T> h = Next;
int count = 0;
while (h != null) {
h = h.getNext();
count++;
}
return count;
}
//remove first node and return (keep)data to the user{you can also remove the last node in the testing}
public T removeFirst() {
if (Next == null) {
return null;
}
DoubleLinkList h =Next;
T data = Next.getData();
Next= Next.getNext();
h.setNext(null);
return data;
}
public DoubleLinkList deleteLast(){
DoubleLinkList temp = Next;
if ( prev== null)
return null;
else
Next.prev.Next = null;
Next = Next.prev;
return temp;
}
//reverse the order of the item(make the head in the last item)
public void printReverse() {
DoubleLinkList<T> h = Next;
for (; h != null; h = h.getNext()) {
System.out.println(h.getData());
}
}
public DoubleLinkList<T> find(T data) {
//go over the linked list as usual..
for (DoubleLinkList<T> h = Next; h != null; h = h.getNext()) {
// notice that the data Object should have the equals method overriden correctly.
if (h.getData().equals(data)) {
}
}
return Next;
}
}Main class
public class Main {
public static void main(String[] args) {
DoubleLinkList theList = new DoubleLinkList ();
theList.addFirst(22);
theList.addFirst(44);
theList.addLast(33);
theList.addLast(55);
theList.Print();
theList.printReverse();
theList.size();
theList.addAfter(22, 77);
theList.addAfter(33, 15);
}
}Do I have to add another classes like Node class???
Dose the classes work correctly???