数据结构之线性表泛型实现
程序员文章站
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")); } }
两种线性表的比较:
- 顺序表查找快,但是插入效率低,需要移动元素
- 链接插入效率高,但是查找较慢
- 链表没有空间限制,顺序表有限制.可以实现自动扩容的顺序表,但是扩容后需要重新移动数据