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

Z时代
2024-01-10
分类：综合

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;
	}
}