Content deleted Content added
Move stack class to implementation of List |
→List implementations: Add details about Vector and Stack |
||
Line 101:
===List implementations===
There are several concrete classes that implement <code>List</code>, including {{java|AbstractList}}, {{java|CopyOnWriteArrayList}} and all of their corresponding subclasses.
====
The direct subclasses of {{java|AbstractList}} class include {{java|AbstractSequentialList}}, {{java|ArrayList}} and {{java|Vector}}.
=====ArrayList class=====
The '''{{Javadoc|module=java.base|package=java.util|class=ArrayList|monotype=y}}''' class implements the <code>List</code> as an array. Whenever functions specific to a <code>List</code> are required, the class moves the elements around within the array in order to do it.
=====LinkedList class=====
The '''{{Javadoc|module=java.base|package=java.util|class=LinkedList|monotype=y}}''' class stores the elements in nodes that each have a pointer to the previous and next nodes in the <code>List</code>. The <code>List</code> can be traversed by following the pointers, and elements can be added or removed simply by changing the pointers around to place the node in its proper place.<ref>{{cite web|url=http://docs.oracle.com/javase/7/docs/api/java/util/List.html |title=List (Java Platform SE 7 ) |publisher=Docs.oracle.com |date=2013-06-06 |access-date=2013-08-16}}</ref>
====
The {{java|Vector}} class has {{java|Stack}} as its direct subclass. This is an example of a violation of the [[composition over inheritance]] principle in the Java platform libraries, since in [[computer science]], a [[Vector (data structure)|vector]] is generally not a [[Stack (abstract data type)|stack]].{{sfn|Bloch|2018|loc=Chapter §4 Item 18: Favor composition over inheritance|pp=87-92}} Composition would have been more appropriate in this scenario.{{sfn|Bloch|2018|loc=Chapter §4 Item 18: Favor composition over inheritance|pp=87-92}}
Stacks are created using '''{{Javadoc|module=java.base|package=java.util|class=Stack|monotype=y}}'''. The <code>Stack</code> offers methods to put a new object on the <code>Stack</code> (method {{Javadoc:SE|module=java.base|name=push(E e)|java/util|Stack|push(E)}}) and to get objects from the <code>Stack</code> (method {{Javadoc:SE|module=java.base|name=pop()|java/util|Stack|pop()}}). A <code>Stack</code> returns the object according to [[Stack (abstract data type)|last-in-first-out]] (LIFO), e.g. the object which was placed latest on the <code>Stack</code> is returned first. <code>java.util.Stack</code> is a standard implementation of a stack provided by Java. The <code>Stack</code> class represents a last-in-first-out (LIFO) stack of objects. It <code>[[inheritance (object-oriented programming)|extends]]</code> class '''{{Javadoc:SE|module=java.base|package=java.util|java/util|Vector}}''' with five operations that allow a <code>Vector</code> to be treated as a <code>Stack</code>. The usual {{Javadoc:SE|module=java.base|name=push(E e)|java/util|Stack|push(E)}} and {{Javadoc:SE|module=java.base|name=pop()|java/util|Stack|pop()}} operations are provided, as well as a method ({{Javadoc:SE|module=java.base|name=peek()|java/util|Stack|peek()}}) to peek at the top item on the <code>Stack</code>, a method to test for whether the <code>Stack</code> is empty ({{Javadoc:SE|module=java.base|name=empty()|java/util|Stack|empty()}}), and a method to search the <code>Stack</code> for an item and discover how far it is from the top ({{Javadoc:SE|module=java.base|name=search(Object o)|java/util|Stack|search(java.lang.Object)}}). When a <code>Stack</code> is first created, it contains no items.▼
=====Stack class=====
The Stack class <code>[[inheritance (object-oriented programming)|extends]]</code> class '''{{Javadoc:SE|module=java.base|package=java.util|java/util|Vector}}''' with five operations that allow a <code>Vector</code> to be treated as a <code>Stack</code>.
Stacks are created using '''{{Javadoc|module=java.base|package=java.util|class=Stack|monotype=y}}'''. The <code>Stack</code> offers methods to put a new object on the <code>Stack</code> (method {{Javadoc:SE|module=java.base|name=push(E e)|java/util|Stack|push(E)}}) and to get objects from the <code>Stack</code> (method {{Javadoc:SE|module=java.base|name=pop()|java/util|Stack|pop()}}). A <code>Stack</code> returns the object according to [[Stack (abstract data type)|last-in-first-out]] (LIFO), e.g. the object which was placed latest on the <code>Stack</code> is returned first. <code>java.util.Stack</code> is a standard implementation of a stack provided by Java.
▲
==Queue interfaces==
| |||