首页 > 代码库 > 线性表 顺序存储 链式存储 ---java实现

线性表 顺序存储 链式存储 ---java实现

首先抽象出一个线性表抽象类(包含基本的增删操作)

public abstract class MyAbstractList<E> {
	public abstract void add(E t);
	public abstract void add(int index,E t);
	public abstract void remove();
	public abstract void remove(int index);
	public abstract int getCount();
	public abstract E get(int index);
	public abstract String toString();
	public abstract boolean contains(E e);
}

ArrayList2继承抽象类,并实现其中的所有抽象方法

public class ArrayList2<E> extends MyAbstractList<E>{
	private E[] e;
	private int len;
	private int size;
	
	ArrayList2(){
		this.size = 0;
		this.len = 10;
		this.e =  (E[]) new Object[len];
	}
	
	@Override
	public void add(E t) {
		// TODO Auto-generated method stub
		ensureCap();
		e[size] = t;
		size++;
	}

	private void ensureCap() {
		// TODO Auto-generated method stub
		if(getCount()>=len){
			E[] temp = (E[]) new Object[len*2+1];
			len = len*2+1;
			for(int i=0;i<len;i++){
				temp[i] = e[i];
			}
		}
	}

	@Override
	public void add(int index, E t) {
		// TODO Auto-generated method stub
		ensureCap();
		for(int i=size-1;i>=index;i--){
			e[i+1] = e[i];
		}
		e[index] = t;
		size++;
	}

	@Override
	public void remove() {
		// TODO Auto-generated method stub
		e[size] = null;
		size--;
	}

	@Override
	public void remove(int index) {
		// TODO Auto-generated method stub
		for(int i=index;i<size-1;i++){
			e[index]  = e[index+1];
		}
		e[size] = null;
		size--;
	}
	
	@Override
	public E get(int index){
		if(index>0 && index<size){
			return e[index];
		}
		else return null;
	}

	public boolean isEmpty(){
		return size>0? false : true;
	}
	
	@Override
	public int getCount() {
		// TODO Auto-generated method stub
		return size;
	}

	@Override
	public String toString(){
		StringBuffer sb  = new StringBuffer();
		sb.append("[");
		for(int i=0;i<size-1;i++){
			sb.append(e[i]).append(",");
		}
		sb.append(e[size-1]);
		sb.append("]");
		return sb.toString().trim();
	}
	
	@Override
	public boolean contains(E e1){
		boolean bool = false;
		for(int i=0;i<size;i++){
			if(e[i] == e1){
				bool = true;
			}
		}
		
		return bool;
	}

}

LinkedList2 继承抽象类,并实现方法

public class LinkedList2<E> extends MyAbstractList<E> {

	private int size;
	private Node<E> head;
	
	public LinkedList2(){
		this.size = 0;
		head = null;
	}
	@Override
	public void add(E t) {
		// TODO Auto-generated method stub
		Node<E> e = new Node<E>(t);
		if(size == 0) head = e;
		else{
			Node temp = head;
			while(temp.next!=null){
				temp = temp.next;
			}
			temp.next = e;
			size++;
		}
	}

	@Override
	public void add(int index, E t) {
		// TODO Auto-generated method stub
		if(index == 0 || index>size) add(t);
		else{
			Node current = head;
			Node<E> e = new Node<E>(t);
			for(int i=0;i<index-1;i++){
				current = current.next;
			}
			e.next = current.next;
			current.next = e;
			size++;
		}
	}

	@Override
	public void remove() {
		// TODO Auto-generated method stub
		remove(size-1);
	}

	@Override
	public void remove(int index) {
		// TODO Auto-generated method stub
		if(index == 0)  removeFirst();
		else if(index == size)  removeLast();
		else if(index<0 || index>size) ;
		else{
			Node<E> pre = head;
			for(int i=0;i<index-1;i++){
				pre = pre.next;
			}
			Node<E> current = pre.next;
			pre.next = current.next;
			size--;
		}
	}

	private void removeLast() {
		// TODO Auto-generated method stub
		if(size == 0) ;
		else{
			Node<E> current = head;
			for(int i=0;i<size-2;i++){
				current = current.next;
			}
			current.next = null;
			size--;
		}
	}
	private void removeFirst() {
		// TODO Auto-generated method stub
		head = head.next;
	}
	@Override
	public int getCount() {
		// TODO Auto-generated method stub
		return size;
	}

	@Override
	public E get(int index) {
		// TODO Auto-generated method stub
		Node<E> current = head;
		for(int i=0;i<index-1;i++){
			current = current.next;
		}
		return current.e;
	}

	@Override
	public String toString() {
		// TODO Auto-generated method stub
		StringBuffer sb = new StringBuffer();
		sb.append("[");
		Node<E> current = head;
		for(int i=0;i<size;i++){
			sb.append(current.e).append(",");
		}
		sb.append("]");
		return sb.toString().trim();
	}

	@Override
	public boolean contains(E e) {
		// TODO Auto-generated method stub
		if(size == 0 ) return false;
		else{
			Node<E> current = head;
			for(int i=0;i<size-1;i++){
				if(current.e == e) return true;
				current = current.next;
			}
			return false;
		}
		
	}

}


/**
 * 链表结点
 */
class Node<E>{
	E e;
	Node<E> next;
	Node(){
		this.next = null;
	}
	Node(E ee){
		e = ee;
		next = null;
	}
}