Linked List
- 用多少就申請多少記憶體，
- 鏈表是一種鏈式存盤的線性表，所有元素的記憶體地址不一定連續的，
介面設計
代碼實作
MyList.java(介面)
package com.cyb; public interface MyList<E> { /** * 元素未找到 */ static final int ELEMENT_NOT_FOUND = -1; /** * 清除所有元素 */ void clear(); /** * 元素的數量 * * @return */ int size(); /** * 是否為空 * * @return */ boolean isEmpty(); /** * 是否包含某個元素 * * @param element 元素 * @return */ boolean contains(E element); /** * 添加元素至尾部 * * @param element 元素 */ void add(E element); /** * 在指定索引下標處添加元素 * * @param index 下標索引 * @param element 元素 */ void add(int index, E element); /** * 獲取元素 * * @param index 索引下標 * @return */ E get(int index); /** * 設定index位置的元素 * * @param index 索引下標 * @param element 元素 * @return 原來的元素 */ E set(int index, E element); /** * 移除指定索引處的元素 * * @param index 索引下標 * @return */ E remove(int index); /** * 查看元素的索引 * * @param element 元素 * @return */ int indexOf(E element); }
AbstractMyList.java(抽象類)
package com.cyb; public abstract class AbstractMyList<E> implements MyList<E> { /** * 元素的數量 */ protected int size; /** * /** 元素的個數 * * @return */ public int size() { return size; } /** * 是否為空 * * @return */ public boolean isEmpty() { return size == 0; } /** * 是否包含某個元素 * * @param element 元素 * @return */ public boolean contains(E element) { return indexOf(element) != ELEMENT_NOT_FOUND; } /** * 添加元素到最后面 * * @param element */ public void add(E element) { add(size, element); } protected void outOfBounds(int index) { throw new IndexOutOfBoundsException("Index:" + index + ",Size:" + size); } /** * 范圍檢測 * * @param index 索引下標 */ protected void rangeCheck(int index) { if (index < 0 || index >= size) { outOfBounds(index); } } /** * 范圍檢測 * * @param index 索引下標 */ protected void rangeCheckForAdd(int index) { if (index < 0 || index > size) { outOfBounds(index); } } }
MyArrayList.java
package com.cyb; /** * 自定義ArrayList陣列 * * @author chenyanbin * */ public class MyArrayList<E> extends AbstractMyList<E> { /** * 所有元素 */ private E[] elements; private static final int DEFAULT_CAPACITY = 100; public MyArrayList() { this(DEFAULT_CAPACITY); } @SuppressWarnings("unchecked") public MyArrayList(int capacity) { capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity; elements = (E[]) new Object[capacity]; } /** * 往index位置添加元素 * * @param index 索引下標 * @param element 元素 */ public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacity(size + 1); for (int i = size; i > index; i--) { elements[i] = elements[i - 1]; } elements[index] = element; size++; } /** * 回傳index位置對應的元素 * * @param index 索引下標 * @return */ public E get(int index) { rangeCheck(index); return elements[index]; } /** * 設定index位置的元素 * * @param index 索引下標 * @param element 元素 * @return 原來的元素 */ public E set(int index, E element) { rangeCheck(index); E oldElement = elements[index]; elements[index] = element; return oldElement; } /** * 洗掉index位置對應的元素 * * @param index 索引下標 * @return 洗掉的元素值 */ public E remove(int index) { rangeCheck(index); E result = elements[index]; for (int i = index + 1; i < size; i++) { elements[i - 1] = elements[i]; } elements[--size] = null; return result; } /** * 洗掉物件 * * @param element 物件 */ public void remove(E element) { remove(indexOf(element)); } /** * 查看元素的位置 * * @param element 元素 * @return */ @SuppressWarnings("null") public int indexOf(E element) { if (element == null) { for (int i = 0; i < size; i++) { if (elements[i] == null) return i; } } else { for (int i = 0; i < size; i++) { if (element.equals(elements[i])) return i; } } return ELEMENT_NOT_FOUND; } /** * 清除所有元素 */ public void clear() { for (int i = 0; i < size; i++) { elements[i] = null; } size = 0; } @Override public String toString() { StringBuilder stringBuilder = new StringBuilder(); stringBuilder.append("size=").append(size).append(",["); for (int i = 0; i < size; i++) { // 方式一(推薦) if (i > 0) { stringBuilder.append(","); } stringBuilder.append(elements[i]); // 方式二(不推薦) // if (i!=size-1) { // stringBuilder.append(","); // } } stringBuilder.append("]"); return stringBuilder.toString(); } /** * 保證要有capacity的容量 * * @param capacity 容量 */ private void ensureCapacity(int capacity) { int oldCapacity = elements.length; if (oldCapacity >= capacity) return; // 新容量為舊容量的1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1); @SuppressWarnings("unchecked") E[] newElements = (E[]) new Object[newCapacity]; for (int i = 0; i < size; i++) { newElements[i] = elements[i]; } elements = newElements; System.out.print("容量從" + oldCapacity + "擴展為" + newCapacity + "\n"); } }
MyLinkedList.java
package com.cyb; public class MyLinkedList<E> extends AbstractMyList<E> { private Node<E> first; @Override public void clear() { size = 0; first = null; } @Override public void add(int index, E element) { if (index==0) { first=new Node<E>(element, first); } else { Node<E> prev = node(index-1); prev.next=new Node<E>(element, prev.next); } size++; } @Override public E get(int index) { // TODO Auto-generated method stub return node(index).element; } @Override public E set(int index, E element) { Node<E> node = node(index); E old = node.element; node.element = element; return old; } @Override public E remove(int index) { Node<E> node=first; if (index==0) { first=first.next; } else { Node<E> prev = node(index-1); node=prev.next; prev.next=node.next; } size--; return node.element; } @Override public int indexOf(E element) { if (element == null) { Node<E> node=first; for (int i = 0; i < size; i++) { if (node.element == null) return i; node=node.next; } } else { Node<E> node=first; for (int i = 0; i < size; i++) { if (element.equals(node.element)) return i; node=node.next; } } return ELEMENT_NOT_FOUND; } /** * 獲取index位置對應的節點物件 * * @param index 索引下標 * @return */ private Node<E> node(int index) { rangeCheck(index); Node<E> node = first; for (int i = 0; i < index; i++) { node = node.next; } return node; } @Override public String toString() { StringBuilder stringBuilder = new StringBuilder(); stringBuilder.append("size=").append(size).append(",["); Node<E> node=first; for (int i = 0; i < size; i++) { // 方式一(推薦) if (i > 0) { stringBuilder.append(","); } stringBuilder.append(node.element); // 方式二(不推薦) // if (i!=size-1) { // stringBuilder.append(","); // } node=node.next; } stringBuilder.append("]"); return stringBuilder.toString(); } private class Node<E> { E element; Node<E> next; public Node(E element, Node<E> next) { this.element = element; this.next = next; } } }
Test.java(測驗類)
package com.cyb; public class Test { public static void main(String[] args) { MyList<Integer> list=new MyLinkedList<Integer>(); list.add(10); list.add(20); list.add(30); list.add(2, 21); list.add(list.size(),55); list.remove(0); System.out.println(list); } }
專案結構圖
推薦一個學習演算法的可視化網站：https://visualgo.net/zh
動態陣列的縮容
如果記憶體使用比較緊張，動態陣列有比較多的剩余空間，可以考慮進行縮容操作，
縮容規則
如：剩余空間占總容量的一半時，就進行縮容，
在remove方法中，添加一個縮容方法，
package com.cyb; /** * 自定義ArrayList陣列,有動態縮容操作 * * @author chenyanbin * */ public class MyArrayList2<E> extends AbstractMyList<E> { /** * 所有元素 */ private E[] elements; private static final int DEFAULT_CAPACITY = 100; public MyArrayList2() { this(DEFAULT_CAPACITY); } @SuppressWarnings("unchecked") public MyArrayList2(int capacity) { capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity; elements = (E[]) new Object[capacity]; } /** * 往index位置添加元素 * * @param index 索引下標 * @param element 元素 */ public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacity(size + 1); for (int i = size; i > index; i--) { elements[i] = elements[i - 1]; } elements[index] = element; size++; } /** * 回傳index位置對應的元素 * * @param index 索引下標 * @return */ public E get(int index) { rangeCheck(index); return elements[index]; } /** * 設定index位置的元素 * * @param index 索引下標 * @param element 元素 * @return 原來的元素 */ public E set(int index, E element) { rangeCheck(index); E oldElement = elements[index]; elements[index] = element; return oldElement; } /** * 洗掉index位置對應的元素 * * @param index 索引下標 * @return 洗掉的元素值 */ public E remove(int index) { rangeCheck(index); E result = elements[index]; for (int i = index + 1; i < size; i++) { elements[i - 1] = elements[i]; } elements[--size] = null; trim(); return result; } /** * 洗掉物件 * * @param element 物件 */ public void remove(E element) { remove(indexOf(element)); } /** * 查看元素的位置 * * @param element 元素 * @return */ @SuppressWarnings("null") public int indexOf(E element) { if (element == null) { for (int i = 0; i < size; i++) { if (elements[i] == null) return i; } } else { for (int i = 0; i < size; i++) { if (element.equals(elements[i])) return i; } } return ELEMENT_NOT_FOUND; } /** * 清除所有元素 */ public void clear() { for (int i = 0; i < size; i++) { elements[i] = null; } size = 0; } @Override public String toString() { StringBuilder stringBuilder = new StringBuilder(); stringBuilder.append("size=").append(size).append(",["); for (int i = 0; i < size; i++) { // 方式一(推薦) if (i > 0) { stringBuilder.append(","); } stringBuilder.append(elements[i]); // 方式二(不推薦) // if (i!=size-1) { // stringBuilder.append(","); // } } stringBuilder.append("]"); return stringBuilder.toString(); } /** * 保證要有capacity的容量 * * @param capacity 容量 */ private void ensureCapacity(int capacity) { int oldCapacity = elements.length; if (oldCapacity >= capacity) return; // 新容量為舊容量的1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1); @SuppressWarnings("unchecked") E[] newElements = (E[]) new Object[newCapacity]; for (int i = 0; i < size; i++) { newElements[i] = elements[i]; } elements = newElements; System.out.print("容量從" + oldCapacity + "擴展為" + newCapacity + "\n"); } /** * 縮容 */ private void trim() { int capacity = elements.length; int newCapacity = capacity >> 1; if (size > newCapacity || capacity <= DEFAULT_CAPACITY) return; E[] newElements = (E[]) new Object[newCapacity]; for (int i = 0; i < size; i++) { newElements[i] = elements[i]; } elements = newElements; } }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/86912.html
標籤：其他
下一篇：什么是哈希表？