Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Created by Julio Tentor <jtentor@fi.unju.edu.ar>
- //
- import java.lang.Comparable;
- import java.util.Iterator;
- public class DoubleLinkedListIteratorComparable<ELEMENT extends Comparable<ELEMENT>> implements Iterable<ELEMENT> {
- private class Node {
- public ELEMENT item;
- public Node next;
- public Node prev;
- public Node() {
- this(null, null, null);
- }
- public Node(ELEMENT item) {
- this(item, null, null);
- }
- public Node(ELEMENT item, Node next) {
- this(item, next, null);
- }
- public Node(ELEMENT item, Node next, Node prev) {
- this.item = item;
- this.next = next;
- this.prev = prev;
- }
- @Override
- public String toString() {
- return this.item.toString();
- }
- }
- private Node head;
- private int count;
- private Node tail;
- public int size() {
- return this.count;
- }
- public DoubleLinkedListIteratorComparable() {
- this.head = null;
- this.count = 0;
- this.tail = null;
- }
- public void addFirst(ELEMENT item) {
- Node temp = new Node(item, this.head, null);
- if (this.count == 0) {
- this.tail = temp;
- }
- else {
- this.head.prev = temp;
- }
- this.head = temp;
- ++this.count;
- }
- public void addLast(ELEMENT item) {
- Node temp = new Node(item, null, this.tail);
- if (this.count == 0) {
- this.head = temp;
- }
- else {
- this.tail.next = temp;
- }
- this.tail = temp;
- ++this.count;
- }
- public ELEMENT removeFirst() {
- if (this.count == 0) {
- throw new RuntimeException("La lista está vacía...");
- }
- ELEMENT item = this.head.item;
- this.head = this.head.next;
- if (this.head == null) {
- this.tail = null;
- }
- else {
- this.head.prev = null;
- }
- --this.count;
- return item;
- }
- public ELEMENT removeLast() {
- if (this.count == 0) {
- throw new RuntimeException("La lista está vacía...");
- }
- ELEMENT item = this.tail.item;
- if (this.head.next == null) {
- this.head = this.tail = null;
- } else {
- this.tail = this.tail.prev;
- this.tail.next = null;
- }
- --this.count;
- return item;
- }
- @Override
- public Iterator<ELEMENT> iterator() {
- return new MyIterator(this.head);
- }
- private class MyIterator implements Iterator<ELEMENT> {
- private Node current;
- public MyIterator(Node current) {
- this.current = current;
- }
- @Override
- public boolean hasNext() {
- return this.current != null;
- }
- @Override
- public ELEMENT next() {
- if (!this.hasNext()) {
- throw new RuntimeException("La lista está vacía...");
- }
- ELEMENT item = this.current.item;
- this.current = this.current.next;
- return item;
- }
- }
- public void addInOrder(ELEMENT item) {
- if (this.count == 0) {
- this.head = this.tail = new Node(item, null, null);
- ++this.count;
- }
- else {
- if (item.compareTo(this.head.item) <= 0) {
- this.addFirst(item);
- }
- else {
- if (item.compareTo(this.tail.item) > 0) {
- this.addLast(item);
- }
- else {
- Node skip = this.head;
- while ((skip != null) && (item.compareTo(skip.item) > 0)) {
- skip = skip.next;
- }
- if (skip == null) {
- throw new RuntimeException("Algo está mal en el orden de los elementos de la lista...");
- }
- else {
- Node temp = new Node(item, skip, skip.prev);
- skip.prev.next = temp;
- skip.prev = temp;
- ++this.count;
- }
- }
- }
- }
- }
- public boolean findAndRemove(ELEMENT item) {
- if (this.count == 0) {
- return false;
- }
- Node skip = this.head;
- while ((skip != null) && !(item.compareTo(skip.item) == 0)) {
- skip = skip.next;
- }
- if (skip == null) {
- return false;
- }
- else {
- if (skip.prev == null) {
- this.removeFirst();
- return true;
- }
- else {
- if (skip.next == null) {
- this.removeLast();
- return true;
- }
- else {
- skip.prev.next = skip.next;
- skip.next.prev = skip.prev;
- skip.prev = skip.next = null;
- return true;
- }
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement