一、顺序表
顺序表本质是使用数组储存数组的一种数据结构，在计算机的储存中是连续的分配内存的。
下面是我自己使用java实现的简单顺序表结构
package list;
public class MyArrayList<E> {
private Object[] data; //数据
private int length; //目前长度
private int size; //容量
//空构造器 默认容量10
public MyArrayList(){
this(10);
}
/**
* 初始化表自定义容量
* @param size
*/
public MyArrayList(int size){
if(size<0){
throw new RuntimeException("定义表容量错误:"+size);
}else {
this.data = new Object[size];
this.size = size;
this.length = 0;
}
}
/**
* 判断容量是否足够，若不够则扩充10
*/
public void SizeIsEnough(){
if(this.length>=this.size){
Object[] newData = new Object[this.size+10];
this.size = size+10;
}
}
/**
* 向表末尾插入一个元素
* @param e 插入的元素
*/
public void add(E e){
data[length++] = e;
}
/**
* 向表的指定位置插入一个元素
* @param e 插入元素的值
* @param index 插入的位置
*/
public void add(E e,int index){
SizeIsEnough();
if(index<0|| index>=length+1){
throw new RuntimeException("插入元素位置错误"+index);
}
for(int i=length++; i>=index; i--){
data[i] = data[i-1];
}
data[index] = e;
}
/**
* 移除指定位置的元素
* @param index 移除元素的位置
*/
public E remove(int index){
if(index<0||index>=length){
throw new RuntimeException("删除元素位置错误"+index);
}
E e = Get(index);
for(int i=index;i<--length;i++){
data[i] = data[i+1];
}
return e;
}
/**
* 移除最后一个元素
* @return 返回被移除的元素
*/
public E remove(){
return remove(length-1);
}
/**
* 获取指定位置的元素
* @param index 获取元素的位置
* @return 获取的元素的值
*/
public E Get(int index){
if(index<0||index>=length){
throw new RuntimeException("查找元素位置错误"+index);
}
E e = (E) data[index];
return e;
}
/**
* 获取指定值的元素的位置
* @param e
* @return
*/
public int Get(E e){
for(int i=0; i<length ;i++) {
if (data[i].equals(e)) {
return i;
}
}
return -1;
}
public int Length() {
return length;
}
public static void main(String[] args) {
MyArrayList<String> list = new MyArrayList<>();
list.add("ming");
list.add("king");
list.add("ling");
for(int i=0;i<list.Length();i++){
System.out.println(list.Get(i));
}
list.remove(2);
list.add("ling",2);
for(int i=0;i<list.Length();i++){
System.out.println(list.Get(i));
}
}
}
二、链表
链表是本质上使用指针储存下一个元素的地址，从而可以在内存中找到下一个元素，形成一个链式的结构。java中没有指针的概念，当时java面向对象的本质就是指针，所以可以使用类作为指针的替代。
以下是我自己实现的简单的单链表
package list;
public class MyLinkList<E> {
private Node<E> head=null;
private int size=0;
/**
* 添加元素
*/
public void add(E e){
Node<E> node = new Node<>();
node.setData(e);
if(head == null){
head = node;
size++;
return;
}
assert false;
Node<E> tmp = head;
while (tmp.hasNext()){
tmp = tmp.getNext();
}
tmp.setNext(node);
size++;
}
/**
* 删除指定位置的元素
* @param index
* @return
*/
public E remove(int index){
Node<E> tmp = head;
Node<E> preNode;
Node<E> currNode;
int count=0;
if(index < 0 || index >size-1){
throw new RuntimeException("删除位置错误"+index);
}
while (tmp.hasNext()&&count != index-1){
tmp = tmp.getNext();
count++;
}
preNode = tmp;
currNode = tmp.getNext();
assert currNode != null;
preNode.setNext(currNode.getNext());
size--;
return currNode.getData();
}
public int Size(){
return size;
}
/**
* 移除链表尾部元素
* @return
*/
public E remove(){
return remove(size-1);
}
/**
* 获取指定位置的元素
* @param index
* @return
*/
public E get(int index){
Node<E> tmp = head;
int count=0;
if(index < 0 || index > size-1){
throw new RuntimeException("查找位置错误"+index);
}
while (tmp.hasNext() && count != index){
tmp = tmp.getNext();
count++;
}
return tmp.getData();
}
public static void main(String[] args) {
MyLinkList<String> linked = new MyLinkList<>();
linked.add("ming");
linked.add("ling");
linked.add("ping");
linked.add("king");
for (int i = 0; i < linked.size; i++) {
System.out.println(linked.get(i));
}
String s = linked.remove();
for (int i = 0; i < linked.size; i++) {
System.out.println(linked.get(i));
}
System.out.println(s);
}
}
class Node<E> {
private E data;
private Node<E> next = null;
public E getData() {
return data;
}
public void setData(E data) {
this.data = data;
}
public Node<E> getNext() {
return next;
}
public void setNext(Node<E> next) {
this.next = next;
}
public boolean hasNext(){
return next != null;
}
}
实现线性表有两种方式。第一种是使用外汇返佣http://www.fx61.com/数组存储线性表的元素。数组是动态创建的。超过数组的容量时，创建一个新的更大的数组，并且将当前数组中的元素复制到新建的数组中。另一种方法是用链表结构实现。链表由节点组成，每个结点都是动态生成的，用来存储一个元素。所有的结点连接成一个线性表。
本文讲述使用变长数组实现线性表
实现代码
package com.billJiang.array;
import java.util.Arrays;
import java.util.Collection;
/**
* Created by billJiang on 2016/11/30.
* 变长数组
*/
public class ArrayList<T> {
private static final int INITIAL_SIZE = 10;
private int size = 0;
private T[] array;
public ArrayList(int initial) {
if (initial <= 0)
initial = INITIAL_SIZE;
array = (T[]) new Object[initial];
}
public void add(T item) {
//数组扩容
if (size == array.length) {
array = Arrays.copyOf(array, size * 2);
}
array[size++] = item;
}
public T get(int index) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException("获取的元素超出了数组的界限");
}
return array[index];
}
public T set(int index, T item) {
T oldItem = this.get(index);
array[index] = item;
return oldItem;
}
public int size() {
return this.size;
}
}
测试代码
package com.billJiang.array;
/**
* Created by billJiang on 2016/11/30.
*/
public class ArrayListTest {
public static void main(String[] args) {
ArrayList<Integer> arrayList=new ArrayList<Integer>(3);
arrayList.add(new Integer(1));
arrayList.add(new Integer(2));
arrayList.add(new Integer(3));
System.out.println(arrayList.size());
arrayList.add(new Integer(4));
arrayList.set(3,5);
System.out.println(arrayList.size());
}
}