欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构之线性表泛型实现

程序员文章站 2022-07-10 21:09:31
...

概述

线性表主要有两种存储方式,分别是顺序存储以及链式存储.顺序存储一般使用数组来实现,链式存储用引用,相当于C语言中的指针.在Java的集合类中,ArrayList可以用来代表顺序表,LinkedList可以代表链表.

本来简单描述自定义的顺序表以及连接,并且引入Java泛型

 

IList接口

首先,我们定义一个IList接口:

 

package com.james.list;

public interface IList<T> {
	public void clear();
	public boolean isEmpty();
	public int length();
	public T get(int i) throws Exception;
	public void insert(int index, T x) throws Exception;
	public void remove(int index) throws Exception;
	public int indexOf(T x);
	public void display();
}

 

 

自定义ArrayList实现以及测试

 

package com.james.list;

import java.util.Arrays;

public class MyArrayList<T> implements IList<T> {
	private T[] elem;
	private int currLen;

	public MyArrayList(int maxSize) {
		currLen=0;
		elem = (T[])new Object[maxSize];
	}

	public void clear() {
		currLen=0;	
	}

	public boolean isEmpty() {
		return (currLen == 0);
	}

	public int length() {
		return currLen;
	}

	public T get(int i) throws Exception {
		if (i<0 || i> currLen -1)
			throw new Exception("The element is not existed for index: " + i);
		return elem[i];
	}

	public void insert(int index, T x) throws Exception {
		if (currLen == elem.length)
			throw new Exception("The list is full");
		if(index<0 ||index>currLen)
			throw new Exception("Wrong insert location");
		for (int j= currLen; j>index; j--)
			elem[j] = elem[j-1];
		elem[index] = x;
		currLen++;
	}

	public void remove(int index) throws Exception {
		if (index<0 || index>currLen -1)
			throw new Exception("Wrong deletion order");
		for (int j=index; j<currLen ;j++)
			elem[j] = elem[j+1];
		
		currLen--;
		
	}

	public int indexOf(T x) {
		int index = 0;
		while (index<currLen && !elem[index].equals(x)){
			index++;
		}
		if (index<currLen)
			return index;
		else
			return -1;
	}

	public void display() {
		for (int index =0; index<currLen; index++) 
			System.out.print(elem[index] + " ");
		System.out.println();
		
	}
	
	public static void main(String[] arg) throws Exception{
		IList arrList = new MyArrayList<String>(10);
		arrList.insert(0, "hellow");
		arrList.insert(1, "world");
		arrList.insert(2, "james");
		arrList.insert(3, "hank");
		
		arrList.display();
		System.out.println("The index of james is: " + arrList.indexOf("james"));
		
		arrList.remove(0);
		arrList.display();
		
		arrList.insert(2, "second");
		arrList.display();
		
		
	}
}

 

 

自定义的Node类

package com.james.list;

public class Node<T> {
	private T data;
	private Node next;
	
	public Node(){
		this(null, null);
	}
	
	public Node(T data){
		this(data, null);
	}
	public Node(T data, Node next) {
		this.data = data;
		this.next = next;
	}

	public T getData() {
		return data;
	}

	public void setData(T data) {
		this.data = data;
	}

	public Node getNext() {
		return next;
	}

	public void setNext(Node next) {
		this.next = next;
	}	

}

 

简单的LinkedList实现:

package com.james.list;

public class MyLinkedList<T> implements IList<T> {
	private Node head;	

	public MyLinkedList() {
		head = new Node();
	}


	public void clear() {
		head.setData(null);
		head.setNext(null);
		
	}


	public boolean isEmpty() {
		return head.getNext() == null;
	}


	public int length() {
		Node first = head.getNext();;
		int length = 0;
		while (first != null) {
			++length;
		}
		return length;
	}

	public T get(int index) throws Exception {
		Node curr = head.getNext();
		int i =0;
		while(curr.getNext()!=null && i<index){
			curr = curr.getNext();
			++i;
		}
		if(i>index || curr==null){
			throw new Exception("Get Wrong location from List");
		}
		
		return (T)curr.getData();
		
	}

	public void insert(int index, T x) throws Exception {
		Node curr = head;
		int j = -1;
		while(curr!=null && j<index-1){
			curr=curr.getNext();
			++j;
		}
		if(j>index-1 || curr == null){
			throw new Exception(" Wrong insert location");
		}
		Node s = new Node(x);
		s.setNext(curr.getNext());
		curr.setNext(s);
		
	}

	public void remove(int index) throws Exception {
		Node currNode = head;
		int i = -1;
		while(currNode.getNext()!=null && i < index-1){
			currNode=currNode.getNext();
			++i;
		}
		if(i> index-1 || currNode.getNext() == null){
			throw new Exception("Illegal deletion location");
		}
		currNode.setNext(currNode.getNext().getNext());
		
		
	}

	public int indexOf(T x) {
		Node currNode = head.getNext();
		int index = 0;
		while(currNode != null && !currNode.getData().equals(x)) {			
			currNode = currNode.getNext();
			++index;
		}
		if (currNode!=null)
			return index;
		else
			return -1;
	}

	public void display() {
		Node currNode = head.getNext();
		while(currNode!=null){
			System.out.println(currNode.getData()+ " ");
			currNode = currNode.getNext();
		}
		
	}
	public static void main(String[] arg) throws Exception{
		MyLinkedList ml = new MyLinkedList<String>();
		ml.insert(0, "jingshou1");
		ml.insert(1, "jingshou2");
		ml.insert(2, "jingshou3");
		ml.insert(3, "jingshou4");		
		ml.display();
		
		ml.remove(1);
		ml.display();
		
		System.out.println(ml.indexOf("jingshou4"));		
		
	}

}

 

两种线性表的比较:

  1. 顺序表查找快,但是插入效率低,需要移动元素
  2. 链接插入效率高,但是查找较慢
  3. 链表没有空间限制,顺序表有限制.可以实现自动扩容的顺序表,但是扩容后需要重新移动数据