Java Tutorial/Collections/Your LinkedList
Содержание
- 1 A class that wraps an array with a List interface.
- 2 A doubly-linked list
- 3 A simple Doubly Linked list class, designed to avoid O(n) behaviour on insert and delete.
- 4 A simple linked List implementation
- 5 Demonstrating linked list
- 6 Double-Ended Lists: list with first and last references
- 7 Finding and Deleting Specified Links
- 8 Iterators on a linked list
- 9 Linked List Entry
- 10 List containing other lists
- 11 List implementation with lazy array construction and modification tracking.
- 12 Sorted Lists
A class that wraps an array with a List interface.
/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements. See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership. The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied. See the License for the
* specific language governing permissions and limitations
* under the License.
*/
import java.lang.reflect.Array;
import java.util.AbstractList;
/**
* A class that wraps an array with a List interface.
*
* @author Chris Schultz <chris@christopherschultz.net$gt;
* @version $Revision: 685685 $ $Date: 2006-04-14 19:40:41 $
* @since 1.6
*/
public class ArrayListWrapper extends AbstractList
{
private Object array;
public ArrayListWrapper(Object array)
{
this.array = array;
}
public Object get(int index)
{
return Array.get(array, index);
}
public Object set(int index, Object element)
{
Object old = get(index);
Array.set(array, index, element);
return old;
}
public int size()
{
return Array.getLength(array);
}
}
A doubly-linked list
class Link {
public int iData;
public Link next;
public Link previous;
public Link(int id) {
iData = id;
}
public String toString() {
return "{" + iData + "} ";
}
}
class DoublyLinkedList {
private Link first;
private Link last;
public DoublyLinkedList() {
first = null;
last = null;
}
public boolean isEmpty() {
return first == null;
}
public void insertFirst(int dd) {
Link newLink = new Link(dd);
if (isEmpty()){
last = newLink;
}else{
first.previous = newLink;
}
newLink.next = first;
first = newLink;
}
public void insertLast(int dd) {
Link newLink = new Link(dd);
if (isEmpty()){
first = newLink;
}else {
last.next = newLink;
newLink.previous = last;
}
last = newLink;
}
public Link deleteFirst() {
Link temp = first;
if (first.next == null){
last = null;
}else{
first.next.previous = null;
}
first = first.next;
return temp;
}
public Link deleteLast() {
Link temp = last;
if (first.next == null){
first = null;
}else{
last.previous.next = null;
}
last = last.previous;
return temp;
}
public boolean insertAfter(int key, int dd) {
Link current = first;
while (current.iData != key) {
current = current.next;
if (current == null){
return false;
}
}
Link newLink = new Link(dd);
if (current == last) {
newLink.next = null;
last = newLink;
} else {
newLink.next = current.next;
current.next.previous = newLink;
}
newLink.previous = current;
current.next = newLink;
return true;
}
public Link deleteKey(int key) {
Link current = first;
while (current.iData != key) {
current = current.next;
if (current == null)
return null;
}
if (current == first){
first = current.next;
}else{
current.previous.next = current.next;
}
if (current == last){
last = current.previous;
}else{
current.next.previous = current.previous;
}
return current;
}
public String toString() {
String str = "List (first-->last): ";
Link current = first;
while (current != null) {
str += current.toString();
current = current.next;
}
System.out.println("");
System.out.print("List (last-->first): ");
current = last;
while (current != null) {
str += current.toString();
current = current.previous;
}
return str;
}
}
public class MainClass {
public static void main(String[] args) {
DoublyLinkedList theList = new DoublyLinkedList();
theList.insertFirst(22);
theList.insertFirst(44);
theList.insertFirst(66);
theList.insertLast(11);
theList.insertLast(33);
theList.insertLast(55);
System.out.println(theList);
theList.deleteFirst();
theList.deleteLast();
theList.deleteKey(11);
System.out.println(theList);
theList.insertAfter(22, 77);
theList.insertAfter(33, 88);
System.out.println(theList);
}
}
List (last-->first): List (first-->last): {66} {44} {22} {11} {33} {55} {55} {33} {11} {22} {44} {66}
List (last-->first): List (first-->last): {44} {22} {33} {33} {22} {44}
List (last-->first): List (first-->last): {44} {22} {77} {33} {88} {88} {33} {77} {22} {44}
A simple Doubly Linked list class, designed to avoid O(n) behaviour on insert and delete.
/*
Licensed to the Apache Software Foundation (ASF) under one or more
contributor license agreements. See the NOTICE file distributed with
this work for additional information regarding copyright ownership.
The ASF licenses this file to You under the Apache License, Version 2.0
(the "License"); you may not use this file except in compliance with
the License. You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/
/**
* A simple Doubly Linked list class, designed to avoid
* O(n) behaviour on insert and delete.
*
* @author
* @version $Id: DoublyLinkedList.java 475685 2006-11-16 11:16:05Z cam $
*/
public class DoublyLinkedList {
/**
* Basic doubly linked list node interface.
*/
public static class Node {
private Node next = null;
private Node prev = null;
public final Node getNext() { return next; }
public final Node getPrev() { return prev; }
protected final void setNext(Node newNext) { next = newNext; }
protected final void setPrev(Node newPrev) { prev = newPrev; }
/**
* Unlink this node from it"s current list...
*/
protected final void unlink() {
if (getNext() != null)
getNext().setPrev(getPrev());
if (getPrev() != null)
getPrev().setNext(getNext());
setNext(null);
setPrev(null);
}
/**
* Link this node in, infront of nde (unlinks it"s self
* before hand if needed).
* @param nde the node to link in before.
*/
protected final void insertBefore(Node nde) {
// Already here...
if (this == nde) return;
if (getPrev() != null)
unlink();
// Actually insert this node...
if (nde == null) {
// empty lst...
setNext(this);
setPrev(this);
} else {
setNext(nde);
setPrev(nde.getPrev());
nde.setPrev(this);
if (getPrev() != null)
getPrev().setNext(this);
}
}
}
private Node head = null;
private int size = 0;
public DoublyLinkedList() {}
/**
* Returns the number of elements currently in the list.
*/
public synchronized int getSize() { return size; }
/**
* Removes all elements from the list.
*/
public synchronized void empty() {
while(size > 0) pop();
}
/**
* Get the current head element
* @return The current "first" element in list.
*/
public Node getHead() { return head; }
/**
* Get the current tail element
* @return The current "last" element in list.
*/
public Node getTail() { return head.getPrev(); }
/**
* Moves <tt>nde</tt> to the head of the list (equivilent to
* remove(nde); add(nde); but faster.
*/
public void touch(Node nde) {
if (nde == null) return;
nde.insertBefore(head);
head = nde;
}
public void add(int index, Node nde) {
if (nde == null) return;
if (index == 0) {
// This makes it the first element in the list.
nde.insertBefore(head);
head = nde;
} else if (index == size) {
// Because the list is circular this
// makes it the last element in the list.
nde.insertBefore(head);
} else {
Node after = head;
while (index != 0) {
after = after.getNext();
index--;
}
nde.insertBefore(after);
}
size++;
}
/**
* Adds <tt>nde</tt> to the head of the list.
* In perl this is called an "unpop". <tt>nde</tt> should
* not currently be part of any list.
* @param nde the node to add to the list.
*/
public void add(Node nde) {
if (nde == null) return;
nde.insertBefore(head);
head = nde;
size++;
}
/**
* Removes nde from the list it is part of (should be this
* one, otherwise results are undefined). If nde is the
* current head element, then the next element becomes head,
* if there are no more elements the list becomes empty.
* @param nde node to remove.
*/
public void remove(Node nde) {
if (nde == null) return;
if (nde == head) {
if (head.getNext() == head)
head = null; // Last node...
else
head = head.getNext();
}
nde.unlink();
size--;
}
/**
* Removes "head" from list and returns it. Returns null if list is empty.
* @return current head element, next element becomes head.
*/
public Node pop() {
if (head == null) return null;
Node nde = head;
remove(nde);
return nde;
}
/**
* Removes "tail" from list and returns it. Returns null if list is empty.
* @return current tail element.
*/
public Node unpush() {
if (head == null) return null;
Node nde = getTail();
remove(nde);
return nde;
}
/**
* Adds <tt>nde</tt> to tail of list
*/
public void push(Node nde) {
nde.insertBefore(head);
if (head == null) head = nde;
size++;
}
/**
* Adds <tt>nde</tt> to head of list
*/
public void unpop(Node nde) {
nde.insertBefore(head);
head = nde;
size++;
}
}
A simple linked List implementation
import java.io.Externalizable;
import java.io.IOException;
import java.io.ObjectInput;
import java.io.ObjectOutput;
import java.io.Serializable;
import java.util.NoSuchElementException;
/*
* Copyright 2005 JBoss Inc
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
/**
* This is a simple linked linked implementation. Each node must implement
* </code>LinkedListNode<code> so that it references the node before and after
* it. This way a node can be removed without having to scan the list to find
* it. This class does not provide an Iterator implementation as its designed
* for efficiency and not genericity. There are a number of ways to iterate the
* list.
*
* Simple iterator:
*
* <pre>
* for (LinkedListNode node = list.getFirst(); node != null; node = node.getNext()) {
* }
* </pre>
*
* Iterator that pops the first entry:
*
* <pre>
* for (LinkedListNode node = list.removeFirst(); node != null; node = list.removeFirst()) {
* }
* </pre>
*
*
* @author
*/
interface LinkedListNode extends Externalizable {
/**
* Returns the next node
*
* @return The next LinkedListNode
*/
public LinkedListNode getNext();
/**
* Sets the next node
*
* @param next
* The next LinkedListNode
*/
public void setNext(LinkedListNode next);
/**
* Returns the previous node
*
* @return The previous LinkedListNode
*/
public LinkedListNode getPrevious();
/**
* Sets the previous node
*
* @param previous
* The previous LinkedListNode
*/
public void setPrevious(LinkedListNode previous);
}
interface Iterator extends Serializable {
public Object next();
}
Demonstrating linked list
class Link {
public int iData;
public Link next;
public Link(int id) {
iData = id;
}
public String toString() {
return "{" + iData+ "} ";
}
}
class LinkList {
private Link first;
public LinkList() {
first = null;
}
public boolean isEmpty() {
return (first == null);
}
public void insertFirst(int id) {
Link newLink = new Link(id);
newLink.next = first;
first = newLink;
}
public Link deleteFirst() {
Link temp = first;
first = first.next;
return temp;
}
public String toString() {
String str = "";
Link current = first;
while (current != null) {
str += current.toString();
current = current.next;
}
return str;
}
}
public class MainClass {
public static void main(String[] args) {
LinkList theList = new LinkList();
theList.insertFirst(22);
theList.insertFirst(44);
theList.insertFirst(66);
theList.insertFirst(88);
System.out.println(theList);
while (!theList.isEmpty()) {
Link aLink = theList.deleteFirst();
System.out.print("Deleted " + aLink);
System.out.println("");
}
System.out.println(theList);
}
}
{88} {66} {44} {22}
Deleted {88}
Deleted {66}
Deleted {44}
Deleted {22}
Double-Ended Lists: list with first and last references
class Link {
public int iData;
public Link next;
public Link(int id) {
iData = id;
}
public String toString() {
return "{" + iData + "} ";
}
}
class FirstLastList {
private Link first;
private Link last;
public FirstLastList() {
first = null;
last = null;
}
public boolean isEmpty() {
return first == null;
}
public void insertFirst(int dd) {
Link newLink = new Link(dd);
if (isEmpty())
last = newLink;
newLink.next = first;
first = newLink;
}
public void insertLast(int dd) {
Link newLink = new Link(dd);
if (isEmpty())
first = newLink;
else
last.next = newLink;
last = newLink;
}
public int deleteFirst() {
int temp = first.iData;
if (first.next == null)
last = null;
first = first.next;
return temp;
}
public String toString() {
String str = "";
Link current = first;
while (current != null) {
str += current.toString();
current = current.next;
}
return str;
}
}
public class MainClass {
public static void main(String[] args) {
FirstLastList theList = new FirstLastList();
theList.insertFirst(22);
theList.insertFirst(44);
theList.insertFirst(66);
theList.insertLast(11);
theList.insertLast(33);
theList.insertLast(55);
System.out.println(theList);
theList.deleteFirst();
theList.deleteFirst();
System.out.println(theList);
}
}
{66} {44} {22} {11} {33} {55}
{22} {11} {33} {55}
Finding and Deleting Specified Links
class Link {
public int iData;
public Link next;
public Link(int id) {
iData = id;
}
public String toString() {
return "{" + iData + "} ";
}
}
class LinkList {
private Link first;
public LinkList() {
first = null;
}
public boolean isEmpty() {
return (first == null);
}
public void insertFirst(int id) {
Link newLink = new Link(id);
newLink.next = first;
first = newLink;
}
public Link delete(int key) {
Link current = first;
Link previous = first;
while (current.iData != key) {
if (current.next == null)
return null;
else {
previous = current;
current = current.next;
}
}
if (current == first)
first = first.next;
else
previous.next = current.next;
return current;
}
public Link find(int key) {
Link current = first;
while (current.iData != key) {
if (current.next == null)
return null;
else
current = current.next;
}
return current;
}
public String toString() {
String str = "";
Link current = first;
while (current != null) {
str += current.toString();
current = current.next;
}
return str;
}
}
public class MainClass {
public static void main(String[] args) {
LinkList theList = new LinkList();
theList.insertFirst(22);
theList.insertFirst(44);
theList.insertFirst(66);
theList.insertFirst(88);
System.out.println(theList);
System.out.println(theList.find(22));
Link aLink = theList.delete(44);
System.out.println(theList);
}
}
{88} {66} {44} {22}
{22}
{88} {66} {22}
Iterators on a linked list
class Link {
public int iData;
public Link next;
public Link previous;
public Link(int id) {
iData = id;
}
public String toString() {
return "{" + iData + "} ";
}
}
class LinkList {
private Link first;
public LinkList() {
first = null;
}
public Link getFirst() {
return first;
}
public void setFirst(Link f) {
first = f;
}
public boolean isEmpty() {
return first == null;
}
public ListIterator getIterator() {
return new ListIterator(this);
}
public String toString() {
Link current = first;
String str ="";
while (current != null) {
str += current.toString();
current = current.next;
}
return str;
}
}
class ListIterator {
private Link current;
private Link previous;
private LinkList ourList;
public ListIterator(LinkList list) {
ourList = list;
reset();
}
public void reset() {
current = ourList.getFirst();
previous = null;
}
public boolean atEnd() {
return (current.next == null);
}
public void nextLink() {
previous = current;
current = current.next;
}
public Link getCurrent() {
return current;
}
public void insertAfter(int dd) {
Link newLink = new Link(dd);
if (ourList.isEmpty()) {
ourList.setFirst(newLink);
current = newLink;
} else {
newLink.next = current.next;
current.next = newLink;
nextLink();
}
}
public void insertBefore(int dd) {
Link newLink = new Link(dd);
if (previous == null) {
newLink.next = ourList.getFirst();
ourList.setFirst(newLink);
reset();
} else {
newLink.next = previous.next;
previous.next = newLink;
current = newLink;
}
}
public double deleteCurrent() {
int value = current.iData;
if (previous == null) {
ourList.setFirst(current.next);
reset();
} else {
previous.next = current.next;
if (atEnd())
reset();
else
current = current.next;
}
return value;
}
}
public class MainClass {
public static void main(String[] args) {
LinkList theList = new LinkList();
ListIterator iter1 = theList.getIterator();
iter1.insertAfter(20);
iter1.insertAfter(40);
iter1.insertAfter(80);
iter1.insertBefore(60);
System.out.println(theList);
iter1.reset();
if (!theList.isEmpty() && !iter1.atEnd()){
iter1.nextLink();
}
System.out.println("Returned " + iter1.getCurrent().iData);
iter1.insertBefore(99);
iter1.insertAfter(100);
System.out.println(theList);
}
}
{20} {40} {60} {80}
Returned 40
{20} {99} {100} {40} {60} {80}
Linked List Entry
import java.io.Externalizable;
import java.io.IOException;
import java.io.ObjectInput;
import java.io.ObjectOutput;
/*
* Copyright 2005 JBoss Inc
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
public class LinkedListEntry extends AbstractBaseLinkedListNode {
private static final long serialVersionUID = 400L;
private Object object;
public LinkedListEntry() {
}
public LinkedListEntry(final Object object) {
this.object = object;
}
public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException {
super.readExternal(in);
object = in.readObject();
}
public void writeExternal(ObjectOutput out) throws IOException {
super.writeExternal(out);
out.writeObject(object);
}
public Object getObject() {
return this.object;
}
public int hashCode() {
return this.object.hashCode();
}
public boolean equals(final Object other) {
return this.object.equals( other );
}
}
/**
* Provides a abstract base implementation that an object can extend so that it can be used in a LinkedList.
*
* @see LinkedList
*
* @author
*/
interface LinkedListNode
extends
Externalizable {
/**
* Returns the next node
* @return
* The next LinkedListNode
*/
public LinkedListNode getNext();
/**
* Sets the next node
* @param next
* The next LinkedListNode
*/
public void setNext(LinkedListNode next);
/**
* Returns the previous node
* @return
* The previous LinkedListNode
*/
public LinkedListNode getPrevious();
/**
* Sets the previous node
* @param previous
* The previous LinkedListNode
*/
public void setPrevious(LinkedListNode previous);
}
List containing other lists
/*
* $Id: ListOfLists.java,v 1.1.1.1 2005/04/07 18:36:24 pocho Exp $
*/
import java.util.AbstractList;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
/**
* Creates list containing other lists, access another list"s elements as it would belong
* to this list.
*
* @version $Name: $ - $Revision: 1.1.1.1 $ - $Date: 2005/04/07 18:36:24 $
* TODO Test
*/
public class ListOfLists extends AbstractList {
private Collection lists = new ArrayList();
public ListOfLists(Collection c) {
Iterator it = c.iterator();
Object o;
while (it.hasNext()) {
o = it.next();
if (o instanceof List)
lists.add(o);
else if (o != null)
throw new UnsupportedOperationException(this.getClass().getName() +
" class supports only instances "+
"of java.util.List interface");
}
}
public int size() {
Iterator it = lists.iterator();
int size = 0;
Object o;
while (it.hasNext()) {
o = it.next();
if (o != null)
size += ((List) o).size();
}
return size;
}
public Object get(int index) {
int size = size();
if (index < 0)
throw new IndexOutOfBoundsException("index: " + index +"; size: " + size);
Iterator it = lists.iterator();
while (it.hasNext()) {
List list = (List) it.next();
if (index < list.size()) {
return list.get(index);
}
else
index -= list.size();
}
// if value has not been returned yet - IndexOutOfBoundsException is thrown
throw new IndexOutOfBoundsException("index: " + index +"; size: " + size);
}
/**
* Replaces the element at the specified position in underlying list with the
* specified element.
*
* @param index index of element to replace.
* @param element element to be stored at the specified position.
* @return the element previously at the specified position.
*/
public Object set(int index, Object element) {
int size = size();
if (index < 0)
throw new IndexOutOfBoundsException("index: " + index +"; size: " + size);
Iterator it = lists.iterator();
while (it.hasNext()) {
List list = (List) it.next();
if (index < list.size()) {
return list.set(index, element);
}
else
index -= list.size();
}
// if value has not been returned yet - IndexOutOfBoundsException is thrown
throw new IndexOutOfBoundsException("index: " + index +"; size: " + size);
}
public int indexOf(Object o) {
ListIterator e = listIterator();
if (o==null) {
while (e.hasNext()) {
if (e.next() == null)
return e.previousIndex();
}
}
else {
Object el;
while (e.hasNext()) {
el = e.next();
if (el.equals(o))
return e.previousIndex();
}
}
return -1;
}
public int lastIndexOf(Object o) {
ListIterator e = listIterator(size());
if (o==null) {
while (e.hasPrevious()) {
if (e.previous() == null)
return e.nextIndex();
}
} else {
Object el;
while (e.hasPrevious()) {
el = e.previous();
if (el != null && el.equals(o))
return e.nextIndex();
}
}
return -1;
}
}
List implementation with lazy array construction and modification tracking.
/*
* Copyright (c) 2006-2009, Dennis M. Sosnoski All rights reserved.
*
* Redistribution and use in source and binary forms, with or without modification, are permitted provided that the
* following conditions are met:
*
* Redistributions of source code must retain the above copyright notice, this list of conditions and the following
* disclaimer. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the
* following disclaimer in the documentation and/or other materials provided with the distribution. Neither the name of
* JiBX nor the names of its contributors may be used to endorse or promote products derived from this software without
* specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
* INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
* SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
* WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
import java.util.AbstractList;
import java.util.Iterator;
/**
* List implementation with lazy array construction and modification tracking. The lazy array construction is a minor
* optimization, to save the added overhead of a backing array for lists which are frequently empty. The modification
* tracking feature supports filtered list construction with result caching.
*
* @author Dennis M. Sosnoski
*/
public class LazyList extends AbstractList
{
/** Singleton iterator for empty collection. */
public static final Iterator EMPTY_ITERATOR = new Iterator() {
public boolean hasNext() {
return false;
}
public Object next() {
throw new IllegalStateException("Internal error - no next");
}
public void remove() {
throw new IllegalStateException("Internal error - nothing to remove");
}
};
/** Unmodifiable empty list instance. */
public static final LazyList EMPTY_LIST = new LazyList() {
public void add(int index, Object element) {
throw new UnsupportedOperationException("Internal error: Unmodifiable list");
}
public Object remove(int index) {
throw new UnsupportedOperationException("Internal error: Unmodifiable list");
}
protected void removeRange(int from, int to) {
throw new UnsupportedOperationException("Internal error: Unmodifiable list");
}
};
/** Number of items currently present in list. */
private int m_size;
/** Maximum number of items allowed before resizing. */
private int m_limit;
/** Backing array (lazy instantiation, <code>null</code> if not used). */
private Object[] m_array;
/**
* Make sure space is available for adding to the list. This grows the size of the backing array, if necessary.
*
* @param count
*/
private void makeSpace(int count) {
if (m_limit - m_size < count) {
Object[] copy;
if (m_array == null) {
copy = new Object[count + 4];
} else {
copy = new Object[m_size * 2 + count];
System.arraycopy(m_array, 0, copy, 0, m_size);
}
m_array = copy;
m_limit = copy.length;
}
}
/*
* (non-Javadoc)
*
* @see java.util.AbstractList#get(int)
*/
public Object get(int index) {
if (index >= 0 && index < m_size) {
return m_array[index];
} else {
throw new IndexOutOfBoundsException("Index " + index + " is out of valid range 0-" + (m_size - 1));
}
}
/*
* (non-Javadoc)
*
* @see java.util.AbstractCollection#size()
*/
public int size() {
return m_size;
}
/*
* (non-Javadoc)
*
* @see java.util.AbstractList#add(int, java.lang.Object)
*/
public void add(int index, Object element) {
if (index >= 0 && index <= m_size) {
makeSpace(1);
if (index < m_size) {
System.arraycopy(m_array, index, m_array, index + 1, m_size - index);
}
m_array[index] = element;
m_size++;
modCount++;
} else {
throw new IndexOutOfBoundsException("Index " + index + " is out of valid range 0-" + m_size);
}
}
/*
* (non-Javadoc)
*
* @see java.util.AbstractList#iterator()
*/
public Iterator iterator() {
if (m_size == 0) {
return EMPTY_ITERATOR;
} else {
return super.iterator();
}
}
/*
* (non-Javadoc)
*
* @see java.util.AbstractList#remove(int)
*/
public Object remove(int index) {
if (index >= 0 && index < m_size) {
Object item = m_array[index];
int start = index + 1;
System.arraycopy(m_array, start, m_array, index, m_size - start);
m_array[--m_size] = null;
modCount++;
return item;
} else {
throw new IndexOutOfBoundsException("Index " + index + " is out of valid range 0-" + (m_size - 1));
}
}
/*
* (non-Javadoc)
*
* @see java.util.AbstractList#set(int, java.lang.Object)
*/
public Object set(int index, Object element) {
if (index >= 0 && index < m_size) {
Object item = m_array[index];
m_array[index] = element;
return item;
} else {
throw new IndexOutOfBoundsException("Index " + index + " is out of valid range 0-" + (m_size - 1));
}
}
/*
* (non-Javadoc)
*
* @see java.util.AbstractList#removeRange(int, int)
*/
protected void removeRange(int from, int to) {
if (from >= 0 && to <= m_size) {
int length = m_size - to;
if (length > 0) {
System.arraycopy(m_array, to, m_array, from, length);
}
m_size -= to - from;
for (int i = m_size; i > to;) {
m_array[--i] = null;
}
modCount++;
} else {
throw new IndexOutOfBoundsException("Range of " + from + "-" + to + " exceeds valid range 0-" + m_size);
}
}
/**
* Get modify counter. This supports tracking changes to determine when cached filters need to be updated.
*
* @return count
*/
public int getModCount() {
return modCount;
}
/**
* Remove range of values. This is just a public version of the protected base class method
* {@link #removeRange(int, int)}
*
* @param from
* @param to
*/
public void remove(int from, int to) {
removeRange(from, to);
}
/**
* Compact the list, removing any <code>null</code> values.
*/
public void compact() {
int offset = 0;
while (offset < m_size) {
if (m_array[offset] == null) {
break;
} else {
offset++;
}
}
if (offset < m_size) {
int fill = offset;
while (++offset < m_size) {
if (m_array[offset] != null) {
m_array[fill++] = m_array[offset];
}
}
m_size = fill;
modCount++;
}
}
}
Sorted Lists
class Link {
public int iData;
public Link next;
public Link(int id) {
iData = id;
}
public String toString() {
return "{" + iData + "} ";
}
}
class SortedList {
private Link first;
public SortedList() {
first = null;
}
public boolean isEmpty() {
return (first == null);
}
public void insert(int key) {
Link newLink = new Link(key);
Link previous = null;
Link current = first;
while (current != null && key > current.iData) {
previous = current;
current = current.next;
}
if (previous == null)
first = newLink;
else
previous.next = newLink;
newLink.next = current;
}
public Link remove() {
Link temp = first;
first = first.next;
return temp;
}
public String toString() {
String str = "";
Link current = first;
while (current != null) {
str += current.toString();
current = current.next;
}
return str;
}
}
public class MainClass {
public static void main(String[] args) {
SortedList theSortedList = new SortedList();
theSortedList.insert(20);
theSortedList.insert(40);
System.out.println(theSortedList);
theSortedList.insert(10);
theSortedList.insert(30);
theSortedList.insert(50);
System.out.println(theSortedList);
theSortedList.remove();
System.out.println(theSortedList);
}
}
{20} {40}
{10} {20} {30} {40} {50}
{20} {30} {40} {50}
