데이터 구조--LinkedList 의 실현
41830 단어 자바데이터 구조 와 알고리즘데이터 구조
Implementations of related methods of LinkedList:
-LinkedList 결점 구조:
/**
* Node is identical to ListNode from the example, but parameterized with T.
*/
private class Node {
//The data field of a node which stores data practical.
public E data;
//A reference to the next node.
public Node next;
/**
* Instantiates a node and at the same time initializes the data field.
*
* @param data Practical data needed to be stored into a node
*/
public Node(E data) {
this.data = data;
this.next = null;
}
/**
* Instantiates a node and at the same time initializes the two fields.
*
* @param data Practical data needed to be stored into a node
* @param next A reference to the next node
*/
public Node(E data, Node next) {
this.data = data;
this.next = next;
}
public String toString() {
return "Node(" + data.toString() + ")";
}
}
-LinkedList 속성 과 구조 방법:
/**
* @param
* @author Zay
* @version 2021/1/4 23:17
*/
public class LinkedList_demo<E> implements List<E> {
// Keeps track of the number of elements
private int size;
// Reference to the first node
private Node head;
/**
* Initializes the size of the list, and the head reference of the list.
*/
public LinkedList_demo() {
head = null;
size = 0;
}
}
-링크 드 리스트 관련 방법:
/**
- Appends the specified element to the end of this list.
- - @param element Element to be appended to this list
- @return Always true
*/
@Override
public boolean add(E element) {
if (head == null) {
head = new Node(element);
} else {
Node node = head;
// loop until the last node
for (; node.next != null; node = node.next) {
}
node.next = new Node(element);
}
size++;
return true;
}
/**
* Inserts the specified element at the specified position in this list.
*
* Shifts the element currently at that position (if any)
* and any subsequent elements to the right (adds one to their indices).
* * @param index Index at which the specified element is to be inserted
* @param element Element to be inserted
*/
@Override
public void add(int index, E element) {
if (index == 0) {
//If the new element is to be inserted at the beginning.
head = new Node(element, head);
} else {
Node node = getNode(index - 1);
node.next = new Node(element, node.next);
}
size++;
}
/**
* Appends all of the elements in the specified collection to the end of this list,
* in the order that they are returned by the specified collection's iterator.
*
* The behavior of this operation is undefined if the specified collection is modified while the operation is in progress.
* (Note that this will occur if the specified collection is this list, and it's non-empty.)
* * @param collection Collection containing elements to be added to this list
* @return True if this list changed as a result of the call
*/
@Override
public boolean addAll(Collection<? extends E> collection) {
boolean flag = true;
for (E element : collection) {
flag &= add(element);
}
return flag;
}
/**
* Retrieves and removes the head (first element) of this list.
* * @param obj Element to be removed from this list, if present
* @return True if this list contained the specified element
*/
@Override
public boolean remove(Object obj) {
int index = indexOf(obj);
if (index == -1) {
return false;
}
remove(index);
return true;
}
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their indices).
* Returns the element that was removed from the list.
* * @param index The index of the element to be removed
* @return The element previously at the specified position
*/
@Override
public E remove(int index) {
E element = get(index);
//The special condition here is that the index is 0.
if (index == 0) {
head = head.next;
} else {
Node node = getNode(index - 1);
node.next = node.next.next;
}
size--;
return element;
}
/**
* Removes from this list all of its elements that are contained in the specified collection.
* * @param collection The specified collection.
* @return Whether removing successfully or not.
*/
@Override
public boolean removeAll(Collection<?> collection) {
boolean flag = true;
for (Object obj : collection) {
flag &= remove(obj);
}
return flag;
}
/**
* Removes all of the elements from this list. The list will be empty after this call returns.
*/
@Override
public void clear() {
head = null;
size = 0;
}
/**
* Returns true if this list contains the specified element. More formally,
* returns true if and only if this list contains at least one element e such that (o==null ? e==null : o.equals(e)).
* * @param obj Element whose presence in this list is to be tested
* @return True if this list contains the specified element
*/
@Override
public boolean contains(Object obj) {
return indexOf(obj) != -1;
}
/**
* Judge whether the linked list contains all the elements in the specified collection.
* * @param collection The specified collection to be judged.
* @return Whether the linked list contains all the elements in the specified collection.
*/
@Override
public boolean containsAll(Collection<?> collection) {
for (Object obj : collection) {
if (!contains(obj)) {
return false;
}
}
return true;
}
/**
* Returns the element at the specified position in this list.
* * @param index Index of the element to return
* @return The element at the specified position in this list
*/
@Override
public E get(int index) {
Node node = getNode(index);
return node.data;
}
/**
* Returns the node at the given index.
* * @param index The index of the specific position
* @return The node at the given index
*/
private Node getNode(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
Node node = head;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
/**
* Returns the index of the first occurrence of the specified element in this list,
* or -1 if this list does not contain the element.
*
* More formally, returns the lowest index i such that (o==null ? get(i)==null : o.equals(get(i))),
* or -1 if there is no such index.
* * @param target Element to search for
* @return The index of the first occurrence of the specified element in this list,
* or -1 if this list does not contain the element
*/
@Override
public int indexOf(Object target) {
Node node = head;
for (int i = 0; i < size; i++) {
//Once find the target, return the index.
if (equals(target, node.data)) {
return i;
}
node = node.next;
}
return -1;
}
/**
* Returns the index of the last occurrence of the specified element in this list,
* or -1 if this list does not contain the element.
*
* More formally, returns the highest index i such that (o==null ? get(i)==null : o.equals(get(i))),
* or -1 if there is no such index.
* * @param target Element to search for
* @return The index of the last occurrence of the specified element in this list, or -1 if this list does not contain the element
*/
@Override
public int lastIndexOf(Object target) {
Node node = head;
int index = -1;
for (int i = 0; i < size; i++) {
//Don't return the index until the whole list is iterated.
if (equals(target, node.data)) {
index = i;
}
node = node.next;
}
return index;
}
/**
* Checks whether an element of the array is the target.
*
* Handles the special case that the target is null.
* * @param target The target
* @param element The element to be compared with the target
*/
private boolean equals(Object target, Object element) {
if (target == null) {
return element == null;
} else {
return target.equals(element);
}
}
/**
* Returns true if this list contains no elements.
* * @return Whether the list contains elements or not.
*/
@Override
public boolean isEmpty() {
return size == 0;
}
/**
* Returns an iterator over the elements in this list (in proper sequence).
* * @return An iterator over the elements in this list.
*/
@Override
public Iterator<E> iterator() {
//Convert the linked list into an array list, then convert the array list into a list,
//then get the iterator from the list.
E[] array = (E[]) toArray();
return Arrays.asList(array).iterator();
}
/**
* Replaces the element at the specified position in this list with the specified element.
* * @param index Index of the element to replace
* @param element Element to be stored at the specified position
* @return The element previously at the specified position
*/
@Override
public E set(int index, E element) {
Node node = getNode(index);
E previous = node.data;
node.data = element;
return previous;
}
/**
* Returns the number of elements in this list.
* * @return The number of elements in this list
*/
@Override
public int size() {
return size;
}
/**
* Returns a view of the portion of this list between the specified fromIndex, inclusive, and toIndex, exclusive.
* (If fromIndex and toIndex are equal, the returned list is empty.)
* The returned list is backed by this list,
* so non-structural changes in the returned list are reflected in this list,
* and vice-versa. The returned list supports all of the optional list operations.
* * @param fromIndex Low endpoint (inclusive) of the subList.
* @param toIndex High endpoint (exclusive) of the subList.
* @return A view of the specified range within this list.
*/
@Override
public List<E> subList(int fromIndex, int toIndex) {
if (fromIndex < 0 || toIndex >= size || fromIndex > toIndex) {
throw new IndexOutOfBoundsException();
}
// TODO: classify this and improve it.
int i = fromIndex;
LinkedList_demo<E> list = new LinkedList_demo<E>();
for (Node node = getNode(fromIndex); node != null; node = node.next) {
if (i <= toIndex) {
list.add(node.data);
}
i++;
}
return list;
}
/**
* Returns an array containing all of the elements in this list in proper sequence (from first to last element).
*
* @return An array containing all of the elements in this list in proper sequence
*/
@Override
public Object[] toArray() {
Object[] array = new Object[size];
int i = 0;
for (Node node = head; node != null; node = node.next) {
array[i] = node.data;
i++;
}
return array;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Is Eclipse IDE dying?In 2014 the Eclipse IDE is the leading development environment for Java with a market share of approximately 65%. but ac...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
