让我们一起来学习数据结构与算法

哈哈，下面开始学习数据结构和算法，希望自己在学习过程中的总结以及代码可以帮助大家更好的理解数据结构与算法。

首先，我们先学习最简单的顺序表。

第一步给出顺序表的基本定义以及操作

package net.itaem.list;

/**
 * 定义一个接口，表示线性表的基本操作
 * 
 * 
 * 线性表的定义：线性表的数据对象集合为{a1,a2,a3...an}，每个元素类型为：DataType。
 * 除了第一个元素外，都有前驱元素；除了最后一个元素外，都有后继元素；每个元素之间都是一对一的关系
 * 
 * @author 骆宏 qq:846705189
 * */
public interface List<T> {
	
	/**
	 * 在指定下标处增加一个数据元素
	 * @param index 要增加元素的下标
	 * @param element 要增加的数据元素
	 * */
    public void add(int index, T element);
    
    /**
     * 删除指定下标的数据元素，并且返回被删除元素的内容
     * @param index 要删除数据元素的下标
     * @return 返回被删除元素的内容
     * */
    public T remove(int index);
    
    /**
     * 获得元素内容的长度
     * @return 返回数据元素的个数
     * */
    public int size();
    
    /**
     * 清空一个链表
     * */
    public void clear();
    
    
}

package net.itaem.list.impl;

import net.itaem.list.List;

/**
 * 这是采用数组实现的List，相当于java.util.ArrayList
 * 采用数组实现的List，在查找元素上是高效的
 * 
 * @author luohong
 * */
public class ArrayList<T> implements List<T> {

	//顺序表的长度
	private int size;  
	//顺序表的数组大小
	private int length;
	//定义一个数组，保存数据元素，这里不能使用泛型来定义数组，所以采用Object，不过方法会保证类型统一
	Object[] elements;

	/**
	 * 采用默认构造器，该数组的长度为10
	 * */
	public ArrayList(){
		this.length = 10;
	    elements = new Object[10];
	}
	
	/**
	 * 初始化顺序表，指定数组的长度
	 * */
	public ArrayList(int length){
		if(length < 0) throw new RuntimeException("顺序表的长度不能为0");
		if(length > Integer.MAX_VALUE) throw new RuntimeException("顺序表的长度超过有效范围");
		this.length = length;
		elements = new Object[length];
	}

	@Override
	public void add(int index, T element) {
		//检查数据下标
		checkIndex(index);
		
		//顺序表长度达到最大了，此时不允许继续添加元素
		if(size == length) return;
		
		//如果要插入的元素是最后面，直接插入
		if(index == size)
			elements[size] = element;
		else{
			//先移动index到length的元素至index+1到length+1，然后再插入
			for(int i=size-1; i>=index; i--) elements[i+1] = elements[i];
		    elements[index] = element;
		}

		//增加成功，顺序表的长度加1
		size++;

	}
	
	@SuppressWarnings("unchecked")
	@Override
	public T remove(int index) {
		//检查数组下标
		checkIndex(index);
		//强制转型
		T result = null;
		
		//如果是最后一个元素，直接删除并且返回即可
		if(index == size-1) {
			result = (T)elements[index];
		    elements[index] = null;
		}else{
			//先删除指定下标元素，后移动index+1至size-1的元素到index至size-2
			result = (T)elements[index];
			for(int i=index+1; i<size; i++) {
				elements[i-1] = elements[i];
			}
			
			//将最后面的元素变成null，因为该元素已经不存在了
			elements[size-1] = null;
		}
		
		//删除成功，顺序表长度-1
		size--;
		
		return result;
	}

	@Override
	public int size() {
		return size;
	}
	
	public int length(){
		return length;
	}

	@Override
	public void clear() {	
		//将数组应用的元素全部指向null
		for(int i=0; i<length; i++){
			if(elements[i] != null) elements[i] = null;
		}
		
		//修改顺序表的长度
		size = 0;
	}

	
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		for(Object element: elements){
			sb.append(element + ", ");
		}
		//去掉多余的“,”
		String elementStr = sb.substring(0, sb.length()-2);
		
		return "the ArrayList length is " + length + " and the elements of size is " + size + "; elements is " + elementStr; 
	}

	//检查数组下标是否正常可以使用，如果不正常直接抛出运行时异常
	private void checkIndex(int index) {
		if(index < 0 || index >= length) throw new RuntimeException("数组下标" + index + "不是有效的，请检查");
	}

	public static void main(String[] args){
		//初始化
		List<Integer> testList = new ArrayList<Integer>(10);
		
		for(int i=0; i<10; i++){
			testList.add(i, i);
		}
		
		System.out.println("before remove\n" + testList);
		System.out.println("remove element is " + testList.remove(8));
		System.out.println("after remove\n" + testList);
		System.out.println("add List in index 5 with value 555");
		testList.add(5, 555);
		System.out.println("after add\n" + testList);
		
		System.out.println("before clear list size " + testList.size());
		testList.clear();
		System.out.println("after clear list size " + testList.size());
		
		System.out.println(testList);
	}
}

before remove
the ArrayList length is 10 and the elements of size is 10; elements is 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
remove element is 8
after remove
the ArrayList length is 10 and the elements of size is 9; elements is 0, 1, 2, 3, 4, 5, 6, 7, 9, null
add List in index 5 with value 555
after add
the ArrayList length is 10 and the elements of size is 10; elements is 0, 1, 2, 3, 4, 555, 5, 6, 7, 9
before clear list size 10
after clear list size 0
the ArrayList length is 10 and the elements of size is 0; elements is null, null, null, null, null, null, null, null, null, null

顺序表，其实在生活中很普遍，是一种最普遍的数据结构。大家通过上面的代码可以看到，通过数组来模拟的顺序表，其实在计算机的实现内部，也就是物理逻辑，也是采用和数据逻辑相同的方式来实现。物理实现过程就好比是计算机内存开辟一个相邻的存储空间，然后按照元素的先后顺序，有序的存储起来。所以这种方式实现的顺序表，在元素查找是快速高效的，因为计算机无论在查找第一个元素和最后一个元素，他们都是同样高效的。

注意点

采用了泛型的技术，但是类里面又是通过数组来实现的。哈哈，关于泛型，暂时先不讨论，大家只要先理解上面的代码即可。

让我们一起来学习数据结构与算法,布布扣,bubuko.com

让我们一起来学习数据结构与算法

原文：http://blog.csdn.net/u010469003/article/details/24554977