- package array;
- import java.util.Arrays;
- /**
- * 基于数组的链表
- *
- * @author 王彪
- *
- */
- public class MyArrayList {
- private static Object[] elements = null;
- private static int size = 0;
- private static final int DEFUAT_INITIAL_CAPACITY = 10;
- public MyArrayList() {
- this(10);
- }
- public MyArrayList(int initialCapacity) {
- if (initialCapacity <0) {
- throw new IllegalArgumentException("输入容量有误");
- }
- elements = new Object[initialCapacity];
- }
- // 初始化数组
- // 保存新元素
- public void add(Object ele) {
- // 数组的扩容问题
- if (size == elements.length) {
- Object[] temp = Arrays.copyOf(elements, elements.length * 2);
- elements = temp;
- }
- elements[size] = ele;
- size++;
- }
- public Object get(int index) {
- if (index < 0 || index>= size) {
- throw new IllegalArgumentException("输入索引有误");
- }
- return elements[index];
- }
- public void set(int index, Object newPlayerNum) {
- if (index <0 || index>= size) {
- throw new IllegalArgumentException("输入索引有误");
- }
- elements[index] = newPlayerNum;
- }
- public void remove(int index) {
- if (index <0 || index>= size) {
- throw new IllegalArgumentException("输入索引有误");
- }
- for (int i = index; i < size - 1; i++) {
- elements[i] = elements[i + 1];
- }
- elements[size - 1] = null;
- size--;
- }
- public String toString() {
- if (elements == null) {
- return null;
- }
- if (size == 0) {
- return "[]";
- }
- StringBuilder sb = new StringBuilder(size * 3 + 1);
- sb.append("[");
- for (int i = 0; i < size; i++) {
- sb.append(elements[i]);
- if (i < size - 1) {
- sb.append(",");
- }
- if (i == size - 1) {
- sb.append("]");
- }
- }
- return sb.toString();
- }
- public int size() {
- return size;
- }
- public boolean isEmpty() {
- return size == 0;
- }
- public void clear() {
- this.elements = new Object[DEFUAT_INITIAL_CAPACITY];
- size = 0;
- }
- }
2. 双向链表
- package linked;
- public class MyLinkedArrayList {
- protected Node first;
- protected Node last;
- protected int size;
- public void addFirst(Object ele) {// 在头部增加
- Node node = new Node(ele);
- if (size == 0) {
- this.first = node;
- this.last = node;
- } else {
- node.next = this.first;
- this.first.prev = node;
- this.first = node;
- }
- size++;
- }
- public void addLast(Object ele) {// 在尾部增加
- Node node = new Node(ele);
- if (size == 0) {
- this.first = node;
- this.last = node;
- } else {
- this.last.next = node;
- node.prev = this.last;
- this.last = node;
- }
- size++;
- }
- public void remove(Object ele) {
- Node current = this.first;
- for (int i = 0; i < size; i++) {
- if (!current.ele.equals(ele)) {
- if (current.next == null) {
- return;
- }
- current = current.next;
- }
- }
- if (current == this.first) {
- this.first = current.next;
- this.first.prev = null;
- } else if (current == this.last) {
- this.last = current.prev;
- this.last.next = null;
- } else {
- current.prev.next = current.next;
- current.next.prev = current.prev;
- }
- size--;
- }
- @Override
- public String toString() {
- if (size == 0) {
- return "[]";
- } else {
- StringBuilder sb = new StringBuilder(size * 3 + 1);
- Node current = this.first;// 第一个节点
- sb.append("[");
- for (int i = 0; i < size; i++) {
- sb.append(current.ele);
- if (i != size - 1) {
- sb.append(",");
- } else {
- sb.append("]");
- }
- current = current.next;
- }
- return sb.toString();
- }
- }
- public class Node {
- public Node(Object ele) {
- this.ele = ele;
- }
- Node prev;
- Node next;
- public Object ele;
- }
- }
3. 双向队列
- package deque;
- import linked.MyLinkedArrayList;
- public class MyDeque extends MyLinkedArrayList {
- public Object getFirst() {
- return this.first.ele;
- }
- public Object getLast() {
- return this.last.ele;
- }
- public void removeFirst(Object ele) {
- super.remove(this.first);
- }
- public void removeLast(Object ele) {
- super.remove(this.last);
- }
- public void addFirst(Object ele) {
- super.addFirst(ele);
- }
- public void addLast(Object ele) {
- super.addLast(ele);
- }
- }
4. 堆
- package stack;
- import array.MyArrayList;
- // 栈
- public class MyStack extends MyArrayList {
- // 入栈
- public void push(Object ele) {
- super.add(ele);
- }
- // 删除栈顶元素
- public void pop() {
- int index = super.size() - 1;
- super.remove(index);
- }
- // 查询栈顶元素
- public Object peek() {
- int index = super.size() - 1;
- return super.get(index);
- }
- }
来源: http://www.bubuko.com/infodetail-2745971.html