List - Single Link List and Double Link List
package com.datastructure.general;
/**
* Created by santosh on 3/4/15.
*/
public interface Collection<E> {
public void put(E element);
public E get(E element);
public boolean contains(E element);
public int indexOf(E element);
public boolean delete(E element);
public int size();
public Iterator<E> getIterator();
}
public interface List<E> extends Collection<E> {
public E getFirst();
public E getLast();
}
public abstract class AbstractList<E> implements List<E> {
protected int size=0;
@Override
public int indexOf(E element) {
int index = -1;
boolean found = false;
Iterator<E> iterator = getIterator();
while (iterator.hasNext()){
++index;
E existingElement = iterator.getNext();
if(existingElement.equals(element)){
found = true;
break;
}
}
if(found) return index;
return -1;
}
@Override
public boolean contains(E element) {
return get(element)!=null;
}
@Override
public int size() {
return this.size;
}
@Override
public E get(E element) {
Iterator<E> iterator = getIterator();
while (iterator.hasNext()){
E elementFound = iterator.getNext();
if(elementFound.equals(element)){
return elementFound;
}
}
return null;
}
}
==================Single Linked List===============
package com.datastructure.general;
/**
* Created by santosh on 7/4/15.
*/
public class SingleLinkedList<E> extends AbstractList<E> {
private Link currentLink;
@Override
public E getFirst() {
return null;
}
@Override
public E getLast() {
return null;
}
private static class Link{
private Object data;
private Link previousLink;
public Object getData() {
return data;
}
public void setData(Object data) {
this.data = data;
}
public Link getPreviousLink() {
return previousLink;
}
public void setPreviousLink(Link previousLink) {
this.previousLink = previousLink;
}
}
@Override
public void put(E element) {
if(this.currentLink==null){
this.currentLink = new Link();
this.currentLink.setData(element);
} else {
Link newLink = new Link();
newLink.setPreviousLink(this.currentLink);
newLink.setData(element);
this.currentLink = newLink;
}
++size;
}
private boolean deleteCurrent(E element){
boolean isDeleted = false;
if(this.currentLink.getData().equals(element)){
this.currentLink = this.currentLink.getPreviousLink();
isDeleted = true;
}
return isDeleted;
}
private boolean deleteFirst(E element){
boolean isDeleted = false;
Link lastButOne = null;
Link indexLink = this.currentLink;
while (indexLink.getPreviousLink()!=null){
lastButOne = indexLink;
indexLink = indexLink.getPreviousLink();
}
if(indexLink.getData().equals(element)){
lastButOne.setPreviousLink(null);
isDeleted = true;
}
return isDeleted;
}
@Override
public boolean delete(E element) {
if(deleteCurrent(element)){--size; return true;}
if(deleteFirst(element)) {--size; return true;}
boolean isDeleted = false;
Link foundLink = null;
Link previousLink = null;
Link priorIteration = null;
Link indexLink = this.currentLink;
while (indexLink.getPreviousLink()!=null){
if(element.equals(indexLink.getData())){
foundLink = indexLink;
previousLink = foundLink.getPreviousLink();
break;
}
priorIteration = indexLink;
indexLink = indexLink.getPreviousLink();
}
if(previousLink!=null && foundLink!=null && priorIteration!=null){
priorIteration.setPreviousLink(previousLink);
--size;
isDeleted = true;
}
return isDeleted;
}
@Override
public Iterator<E> getIterator() {
return new LinkedListIterator(this.currentLink);
}
private static class LinkedListIterator<E> implements Iterator<E>{
private Link currentLink;
private LinkedListIterator(Link currentLink) {
this.currentLink = currentLink;
}
@Override
public boolean hasNext() {
return this.currentLink!=null;
}
@Override
public E getNext() {
Link currentLink = this.currentLink;
this.currentLink = this.currentLink.getPreviousLink();
return (E)currentLink.getData();
}
}
}
================= Double Linked List====================
package com.datastructure.general;
/**
* Created by santosh on 8/4/15.
*/
public class DoubleLinkedList<E> extends AbstractList<E> {
private Node currentNode;
private Node firstNode;
public Node getCurrentNode() {
return currentNode;
}
public void setCurrentNode(Node currentNode) {
this.currentNode = currentNode;
}
@Override
public E getFirst() {
E first = null;
if(firstNode!=null){
first =(E)firstNode.getData();
}
return first;
}
@Override
public E getLast() {
E last = null;
if(currentNode!=null){
last =(E)currentNode.getData();
}
return last;
}
private static class Node{
private Object data;
private Node nextNode;
private Node previousNode;
public Object getData() {
return data;
}
public void setData(Object data) {
this.data = data;
}
public Node getNextNode() {
return nextNode;
}
public void setNextNode(Node nextNode) {
this.nextNode = nextNode;
}
public Node getPreviousNode() {
return previousNode;
}
public void setPreviousNode(Node previousNode) {
this.previousNode = previousNode;
}
}
@Override
public void put(E element) {
if(currentNode==null){
currentNode = new Node();
currentNode.setData(element);
currentNode.setNextNode(null);
currentNode.setPreviousNode(null);
firstNode = currentNode;
} else {
Node newNode = new Node();
newNode.setData(element);
newNode.setPreviousNode(currentNode);
currentNode.setNextNode(newNode);
currentNode = newNode;
}
++size;
}
@Override
public boolean contains(E element) {
return false;
}
@Override
public boolean delete(E element) {
return false;
}
@Override
public int size() {
return 0;
}
@Override
public Iterator<E> getIterator() {
return new DoubleLinkedListIterator<E>(this.firstNode);
}
private class DoubleLinkedListIterator<E> implements Iterator<E>{
private Node toStartNode;
private boolean isLast;
private DoubleLinkedListIterator(Node toStartNode) {
this.toStartNode = toStartNode;
}
@Override
public boolean hasNext() {
boolean hasNext = false;
if(toStartNode!=null){
Node nextNode = toStartNode.getNextNode();
if(nextNode!=null){
hasNext = true;
} else {
hasNext = isLast;
isLast = false;
}
}
return hasNext;
}
@Override
public E getNext() {
Node node = toStartNode;
toStartNode = toStartNode.getNextNode();
if(toStartNode != null && toStartNode.getNextNode()==null){
isLast = true;
}
return (E) node.getData();
}
}
}
package com.datastructure.general;
/**
* Created by santosh on 3/4/15.
*/
public interface Collection<E> {
public void put(E element);
public E get(E element);
public boolean contains(E element);
public int indexOf(E element);
public boolean delete(E element);
public int size();
public Iterator<E> getIterator();
}
public interface List<E> extends Collection<E> {
public E getFirst();
public E getLast();
}
public abstract class AbstractList<E> implements List<E> {
protected int size=0;
@Override
public int indexOf(E element) {
int index = -1;
boolean found = false;
Iterator<E> iterator = getIterator();
while (iterator.hasNext()){
++index;
E existingElement = iterator.getNext();
if(existingElement.equals(element)){
found = true;
break;
}
}
if(found) return index;
return -1;
}
@Override
public boolean contains(E element) {
return get(element)!=null;
}
@Override
public int size() {
return this.size;
}
@Override
public E get(E element) {
Iterator<E> iterator = getIterator();
while (iterator.hasNext()){
E elementFound = iterator.getNext();
if(elementFound.equals(element)){
return elementFound;
}
}
return null;
}
}
==================Single Linked List===============
package com.datastructure.general;
/**
* Created by santosh on 7/4/15.
*/
public class SingleLinkedList<E> extends AbstractList<E> {
private Link currentLink;
@Override
public E getFirst() {
return null;
}
@Override
public E getLast() {
return null;
}
private static class Link{
private Object data;
private Link previousLink;
public Object getData() {
return data;
}
public void setData(Object data) {
this.data = data;
}
public Link getPreviousLink() {
return previousLink;
}
public void setPreviousLink(Link previousLink) {
this.previousLink = previousLink;
}
}
@Override
public void put(E element) {
if(this.currentLink==null){
this.currentLink = new Link();
this.currentLink.setData(element);
} else {
Link newLink = new Link();
newLink.setPreviousLink(this.currentLink);
newLink.setData(element);
this.currentLink = newLink;
}
++size;
}
private boolean deleteCurrent(E element){
boolean isDeleted = false;
if(this.currentLink.getData().equals(element)){
this.currentLink = this.currentLink.getPreviousLink();
isDeleted = true;
}
return isDeleted;
}
private boolean deleteFirst(E element){
boolean isDeleted = false;
Link lastButOne = null;
Link indexLink = this.currentLink;
while (indexLink.getPreviousLink()!=null){
lastButOne = indexLink;
indexLink = indexLink.getPreviousLink();
}
if(indexLink.getData().equals(element)){
lastButOne.setPreviousLink(null);
isDeleted = true;
}
return isDeleted;
}
@Override
public boolean delete(E element) {
if(deleteCurrent(element)){--size; return true;}
if(deleteFirst(element)) {--size; return true;}
boolean isDeleted = false;
Link foundLink = null;
Link previousLink = null;
Link priorIteration = null;
Link indexLink = this.currentLink;
while (indexLink.getPreviousLink()!=null){
if(element.equals(indexLink.getData())){
foundLink = indexLink;
previousLink = foundLink.getPreviousLink();
break;
}
priorIteration = indexLink;
indexLink = indexLink.getPreviousLink();
}
if(previousLink!=null && foundLink!=null && priorIteration!=null){
priorIteration.setPreviousLink(previousLink);
--size;
isDeleted = true;
}
return isDeleted;
}
@Override
public Iterator<E> getIterator() {
return new LinkedListIterator(this.currentLink);
}
private static class LinkedListIterator<E> implements Iterator<E>{
private Link currentLink;
private LinkedListIterator(Link currentLink) {
this.currentLink = currentLink;
}
@Override
public boolean hasNext() {
return this.currentLink!=null;
}
@Override
public E getNext() {
Link currentLink = this.currentLink;
this.currentLink = this.currentLink.getPreviousLink();
return (E)currentLink.getData();
}
}
}
================= Double Linked List====================
package com.datastructure.general;
/**
* Created by santosh on 8/4/15.
*/
public class DoubleLinkedList<E> extends AbstractList<E> {
private Node currentNode;
private Node firstNode;
public Node getCurrentNode() {
return currentNode;
}
public void setCurrentNode(Node currentNode) {
this.currentNode = currentNode;
}
@Override
public E getFirst() {
E first = null;
if(firstNode!=null){
first =(E)firstNode.getData();
}
return first;
}
@Override
public E getLast() {
E last = null;
if(currentNode!=null){
last =(E)currentNode.getData();
}
return last;
}
private static class Node{
private Object data;
private Node nextNode;
private Node previousNode;
public Object getData() {
return data;
}
public void setData(Object data) {
this.data = data;
}
public Node getNextNode() {
return nextNode;
}
public void setNextNode(Node nextNode) {
this.nextNode = nextNode;
}
public Node getPreviousNode() {
return previousNode;
}
public void setPreviousNode(Node previousNode) {
this.previousNode = previousNode;
}
}
@Override
public void put(E element) {
if(currentNode==null){
currentNode = new Node();
currentNode.setData(element);
currentNode.setNextNode(null);
currentNode.setPreviousNode(null);
firstNode = currentNode;
} else {
Node newNode = new Node();
newNode.setData(element);
newNode.setPreviousNode(currentNode);
currentNode.setNextNode(newNode);
currentNode = newNode;
}
++size;
}
@Override
public boolean contains(E element) {
return false;
}
@Override
public boolean delete(E element) {
return false;
}
@Override
public int size() {
return 0;
}
@Override
public Iterator<E> getIterator() {
return new DoubleLinkedListIterator<E>(this.firstNode);
}
private class DoubleLinkedListIterator<E> implements Iterator<E>{
private Node toStartNode;
private boolean isLast;
private DoubleLinkedListIterator(Node toStartNode) {
this.toStartNode = toStartNode;
}
@Override
public boolean hasNext() {
boolean hasNext = false;
if(toStartNode!=null){
Node nextNode = toStartNode.getNextNode();
if(nextNode!=null){
hasNext = true;
} else {
hasNext = isLast;
isLast = false;
}
}
return hasNext;
}
@Override
public E getNext() {
Node node = toStartNode;
toStartNode = toStartNode.getNextNode();
if(toStartNode != null && toStartNode.getNextNode()==null){
isLast = true;
}
return (E) node.getData();
}
}
}