手寫記錄一下~

?

頂級接口List

public interface List<E> {//返回線性表的大小public int getSize();//判斷線性表中是否為空public boolean isEmpty();//判斷線性表中是否包含元素oboolean contains(E o);//在線性表中查找元素o，若成功找到，返回其位置index；否則，返回-1public int indexOf(E e);//獲取線性表中 位置為index的元素public E get(int index);//將線性表中 位置為index的元素設(shè)置為epublic void set(int index, E e);//在線性表中位置為index處添加元素epublic void add(int index, E e);//刪除并返回線性表中位置為index的元素public E remove(int index); }

ArrayList~~~

import java.util.Arrays;public class ArrayList<E> implements List<E> {private static final int DEFAULT_CAPACITY = 10;private E[] data;private int size;public ArrayList(int capacity) {this.size = 0;data = (E[]) new Object[capacity];}public ArrayList() {this(DEFAULT_CAPACITY);}// O(1)@Overridepublic int getSize() {return size;}// O(1)@Overridepublic boolean isEmpty() {return size == 0;}// O(n)@Overridepublic boolean contains(E o) {for (int i = 0; i < size; i++) {if (data[i].equals(o))return true;}return false;}// O(n)@Overridepublic int indexOf(E e) {for (int i = 0; i < size; i++) {if (data[i].equals(e))return i;}return -1;}// O(1)@Overridepublic E get(int index) {if (index < 0 || index >= size)throw new IllegalArgumentException("數(shù)組小標越界...");return data[index];}// O(1)@Overridepublic void set(int index, E e) {if (index < 0 || index >= size)throw new IllegalArgumentException("數(shù)組小標越界...");data[index] = e;}// O(n)@Overridepublic void add(int index, E e) {if (index < 0 || index > size) {throw new IllegalArgumentException("數(shù)組小標越界...");}if (size == data.length) {grow(2 * data.length);}for (int i = size - 1; i >= index; i--) {data[i + 1] = data[i];}data[index] = e;size++;}// 均攤時間復雜度 O(1)public void addLast(E e) {add(size, e);}// O(n)@Overridepublic E remove(int index) {if (index < 0 || index >= size) {throw new IllegalArgumentException("數(shù)組小標越界...");}E val = data[index];for (int i = index + 1; i < size; i++) {data[i - 1] = data[i];}size--;data[size] = null;if (size < (data.length >> 1)) {grow(data.length / 2);}return val;}private void grow(int newCapacity) {/** E[] newData = (E[]) new Object[newCapacity]; for(int i=0;* i<data.length; i++) newData[i] = data[i];* * data = newData;*/data = Arrays.copyOf(data, newCapacity);}public static void main(String[] args) {List<Integer> list = new ArrayList<>();for (int i = 0; i < 100; i++)list.add(i, i);for (int i = 0; i < 100; i++) {System.out.println("The " + i + "th element is: " + list.get(i));}for (int i = 0; i < 50; i += 8) {list.remove(i);}for (int i = 0; i < list.getSize(); i++) {System.out.println("After removing, the " + i + "th element is: " + list.get(i));}}

LinkedList~

public class LinkedList<E> implements List<E> {private class Node {private E data; //數(shù)據(jù)域private Node next; //指針域，指向下一個Nodepublic Node(E data, Node next) {this.data = data;this.next = next;}public Node(E data) {this(data, null);}public String toString() {return data.toString();}}private Node head;//private Node tail;private int size;public LinkedList() {head = null;size = 0;}//O(1)@Overridepublic int getSize() {return size;}//O(1)@Overridepublic boolean isEmpty() {return size == 0;}//O(n)@Overridepublic boolean contains(E o) {Node p = head;while(p != null) {if(p.data.equals(o))return true;p = p.next;}return false;}//O(n)@Overridepublic int indexOf(E e) {int result = -1;Node p = head;int i = 0;while(p != null) {if(p.data.equals(e)){result = i;break;}p = p.next;i++;}return result;}//O(n)@Overridepublic E get(int index) {if(index<0 || index >= size) {throw new IllegalArgumentException("非法下標...");}Node p = head;for(int i=0; i<index; i++)p = p.next;return p.data;}//O(n)@Overridepublic void set(int index, E e) {if(index<0 || index >= size) {throw new IllegalArgumentException("非法下標...");}Node p = head;for(int i=0; i<index; i++)p = p.next;p.data = e; }//O(n)@Overridepublic void add(int index, E e) {if(index < 0 || index > size) {throw new IllegalArgumentException("下標越界.....");}//插到鏈表頭部if(index == 0) {addFirst(e);}else if(index == size) {addLast(e);}else {Node prev = head;for(int i=0; i<index; i++) {prev = prev.next;}prev.next = new Node(e, prev.next);size++;}}//O(1)public void addFirst(E e) {Node node = new Node(e, head);head = node;size++;}//O(n)public void addLast(E e) {Node node = new Node(e, null);//鏈表為空if(head == null) {head = node;}else {Node prev = head;while(prev.next != null) {prev = prev.next;}prev.next = node;}size++;}//O(n)@Overridepublic E remove(int index) {if(index<0 || index >= size) {throw new IllegalArgumentException("非法下標...");}if(index == 0) {return removeFirst();}else if (index == size -1) {return removeLast();}else{Node prev = head;for(int i=0; i<index-1; i++)prev = prev.next;Node tmp = prev.next;prev.next = tmp.next;tmp.next = null;size--;return tmp.data;}}//O(1)public E removeFirst() {if(head == null)return null;E result = head.data;head = head.next;size--;return result;}//O(n)public E removeLast() {if(head == null)return null;E result;//鏈表只有一個節(jié)點if(head.next == null) {result = head.data;head = null;}else {Node prev = head;while(prev.next.next != null)prev = prev.next;result = prev.next.data;prev.next = null;}size--;return result;}public static void main(String[] args) {List<Integer> list = new LinkedList<>();for(int i=0; i<10; i++)list.add(i, i);for(int i=0; i<10; i++) {System.out.println("The " + i + "th element is: " + list.get(i));}list.remove(0);for(int i=0; i<list.getSize(); i++) {System.out.println("After removing, the " + i + "th element is: " + list.get(i));}}}

?

總結(jié)

以上是生活随笔為你收集整理的JAVA手写ArrayList以及LinkedList的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。