一、概念
对于常用的数据结构，可分为线性结构和非线性结构，线性结构主要是线性表，非线性结构主要是数和图。当n>0时，表可表示为：(a0,a1,a2,a3,…an)
1、 线性表的特征：
1、存在唯一的被称作”第一个”的数据元素
2、存在唯一的一个称作”最后一个的”数据元素”
3、除第一个之外，集合中的每个数据元素均只有一个前驱
4、除最后一个之外，集合中每个元素均只有一个后继
2、线性表的基本操作
1、初始化：
2、返回线性表长度
3、获取指定索引处元素
4、按值查找元素位置
5、直接插入数据元素
6、向指定位置插入元素
7、直接删除元素
8、删除指定位置元素
二、顺序存储结构
线性表的顺序结构是指用一组地址连续的存储单元依次存放线性表的元素。下面采用数组实现顺序结构线性表。
import java.util.Arrays;
public class Sequence<T> {
privateObject[] elementData;//定义一个数组
privateint DEFAULT_SIZE = 1; //数组默认大小
privateint capacity; //数组容量
privateint size = 0; //当前数组大小
//初始化
public Sequence(){
capacity= this.DEFAULT_SIZE;
elementData= new Object[capacity];
} public Sequence()(T element){
this();
elementData[0]= element;
size++;
} //返回线性表长度
public int length(){
return this.size;
} //返回指定索引处元素。
public T getElementByIndex(int index){ if(index< 0 || index > (size-1)){
System.out.println("索引范围越界！！！");
System.exit(0);
}
return (T)elementData[index];
}
//按值查找数据元素的位置
public int getIndexByValue(T value){
for(int i = 0; i < elementData.length;i++ ){
if(value.equals(elementData[i])){
return i;
}
}
return -1;//未找到则返回-1
} //向指定位置插入元素
public void insert(T element,int index){
ensureCapacity(); //确保线性表容量够
if(index>= 0 && index < size){
int i = 0;
//将插入位置之后元素挨个后移1
for(i= (size-1); i >= index;i--){
elementData[i+1]= elementData[i];
}
elementData[i+1]= element;//插入该元素
size++; //数组当前容量+1
}
else{
throw new IndexOutOfBoundsException("插入元素位置越界！！！");
}
} //想线性表末尾添加元素
public void add(T element){
ensureCapacity(); //确保线性表容量够
elementData[size]= element;
size++;
} //删除线性表中指定位置元素
public void delete(int index){
if(index>= 0 && index < size){
int i;
//将要删除元素位置之后的元素挨个前移1，通过覆盖删除
for(i= index+1;i < size;i++){
elementData[i-1]= elementData[i];
}
elementData[size-1]= null;
}
else{
thrownew IndexOutOfBoundsException("所要删除元素位置越界！！！");
}
} //删除指定元素
public void delete(T value){
int index = this.getIndexByValue(value);
if(index!= -1){
this.delete(index);
}
else{
System.out.println("您要删除的元素并不存在");
System.exit(0);
}
size--;
} //判断线性表是否为空
public boolean isEmpty(){
boolean b = false;
if(this.length()!= 0){
b= true;
}
return b;
} //清空线性表
public void clear(){
for(Object o:elementData){
o= null;
}
size= 0;
} //显示线性表中所有元素
public void view(){
System.out.print("当前线性表中元素为：");
for(int i = 0;i < size;i++){
System.out.print(elementData[i]+ " ");
}
System.out.print("\n");
} //扩充线性表容量
public void ensureCapacity(){
while((size+1)> capacity){
capacity=capacity * 2; //线性表容量每次增大一倍
elementData= Arrays.copyOf(elementData, capacity);
}
} public static void main(String[] args) {
Sequence<String> sequence = new Sequence<>();
sequence.add("hello");
sequence.add("world");
sequence.add("java");
sequence.add("perfect");
sequence.view();
sequence.insert("haha",1);
sequence.view();
System.out.println("索引为3的元素为：" +sequence.getElementByIndex(3));
System.out.println("字符串perfect的索引号为："+ sequence.getIndexByValue("perfect"));
sequence.delete("hello");
sequence.view();
sequence.clear();
System.out.println("clear之后线性表长度为："+ sequence.length());
}
}
三、链式存储结构
1、概念
链式存储结构的线性表(简称为链表)采用一组任意的存储单元存放线性表中的数据元素。链式存储结构的线性表不是按线性的逻辑顺序来保存数据元素，它需要在每个数据元素里保存一个引用下一个数据元素的引用。
节点 = 数据元素 + 引用下一个节点的引用 + 引用上一个节点的引用
2、单链表基本操作
建立单链表方法：1头插法建表 2尾插法建表
查找操作：1按index查找指定数据元素 2在链表中查找指定的数据元素的index
插入操作：在第index个索引处插入元素
删除操作：删除第index个节点
3、单链表具体实现
public class LinkList<T>{
//定义Node节点
private class Node{
private T data;
private Node next;
public Node(){
}
public Node(T element,Node next){
this.data= element;
this.next= next;
}
}
//成员变量
private Node header;//头节点
private Node tail; //尾节点
private int size = 0; //链表长度
public LinkList(){
header= null;
tail= header;
}
public LinkList(T element){
header= new Node(element,null);
tail= header;
}
//获取链表中指定索引处的元素
public T get(int index){
return this.getNodeByIndex(index).data;
}
//获取链表中指定索引处Node
public Node getNodeByIndex(int index){
this.checkBorder(index);
Node currentNode = header;
for(int i = 0;i < size && currentNode !=null;i++,currentNode =currentNode.next){
if(i== index){
return currentNode;
}
}
return null;
}
//向指定索引处插入元素
public void insert(T element,int index){
this.checkBorder(index);
if(index== 0){
this.addAtHeader(element);
}
else{
NodeprevNode =this.getNodeByIndex(index-1);//获取插入位置的前向Node
prevNode.next=new Node(element,prevNode.next);
}
size++;
}
//删除指定索引处Node
public T delete(int index){
this.checkBorder(index);
Nodedel = null;
//删除的是header
if(index== 0){
del= header;
header= header.next;
}
else{
NodeprevNode =this.getNodeByIndex(index);
del= prevNode.next;
prevNode.next= del.next; //将prevNode的后向Node设置为del.next
del.next= null;
}
size--;
returndel.data;
}
//头插法向链表中添加元素
public void addAtHeader(T element){
header= new Node(element,header);//将新添加的Node的next设置为原先的header，然后将新的Node设置为新的header
if(tail==null){
tail= header;
}
size++;
}
//尾插法
public void add(T element){
//链表为空的情况
if(header==null){
header= new Node(element,null);
tail= header;
}
else{
tail.next= new Node(element, null); //将tail节点的next设置为new Node
tail= tail.next;//将new Node设置为tail
}
size++;
}
//遍历整个链表
public void view(){
NodecurrentNode = header;
System.out.print("当前链表元素：");
while(currentNode!=null){
System.out.print(currentNode.data+ " ");
currentNode= currentNode.next;
}
System.out.println("");
}
//检测索引是否越界
private void checkBorder(int index){
if(index< 0 || index > size-1){
thrownew IndexOutOfBoundsException("链表索引已越界");
}
}
public int length(){
return this.size;
}
public static void main(String args[]){
LinkList<String> linkList =new LinkList<>();
linkList.add("hello");
linkList.add("world");
linkList.addAtHeader("header");
System.out.println("当前链表长度为："+ linkList.length());
linkList.view();
System.out.print("插入test之后,");
linkList.insert("test",2);
linkList.view();
linkList.delete(2);
System.out.print("删除索引2处元素后，");
linkList.view();
System.out.println("索引1处元素为：" +linkList.get(1));
}
}
4、双链表实现
public class DoubleLinkList<T> {
//定义双向链表节点
private class Node{
private T data;
private Node prev;
private Node next;
public Node(){
}
public Node(T element,Node prev,Node next){
this.data= element;
this.prev= prev;
this.next= next;
}
}
private Node header;
private Node tail;
private int size = 0;
public DoubleLinkList(){
header= null;
tail= null;
}
public DoubleLinkList(T element){
header= new Node(element,null,null);
tail= header;
size++;
}
//获取链表长度
public int length(){
return this.size;
}
//检测index是否越界
public void checkBorder(int index){
if(index< 0 || index > size-1){
throw new IndexOutOfBoundsException("链表索引已越界");
}
}
//获取指定索引处Node
public Node getNodeByIndex(int index){
checkBorder(index);//越界检测
if(index< size/2){
NodecurrentNode = header;
for(int i = 0;i < size/2;i++,currentNode = currentNode.next ){
if(i== index){
return currentNode;
}
}
}
else{
NodecurrentNode = tail;
for(int i = size-1;i >= size/2;i--,currentNode = currentNode.prev){
if(i== index){
returncurrentNode;
}
}
}
return null;
}
//获取链表中指定索引处的元素值
public T get(int index){
return this.getNodeByIndex(index).data;
}
//根据元素值查找元素索引
public int locate(T element){
Node currentNode = this.header;
for(int i = 0;i < size-1;i++,currentNode = currentNode.next){
if(currentNode.data.equals(element)){
returni;
}
}
return -1;
}
//向链表中以尾插法添加元素
public void add(T element){
if(size== 0){
header= new Node(element,null,null);
tail= header;
}
else{
Node newNode =new Node(element,tail,null);
tail.next= newNode;
tail= newNode;
}
size++;
}
//头插法向链表添加元素
public void addAtHeader(T element){
if(size== 0){
header= new Node(element,null,null);
tail= header;
}
else{
Node newNode =new Node(element,null,header);
header.prev= newNode;
header= newNode;
}
size++;
}
//根据索引插入元素
public void insert(T element,int index){
this.checkBorder(index);
Node prevNode = this.getNodeByIndex(index-1);
Node nextNode = this.getNodeByIndex(index);
Node insertNode = new Node(element, prevNode, nextNode);
nextNode.prev= insertNode;
prevNode.next= insertNode;
size++;
}
//根据索引删除元素
public void delete(int index){
this.checkBorder(index);
Node prevDelNode = this.getNodeByIndex(index-1);
Node nextDelNode = this.getNodeByIndex(index+1);
prevDelNode.next= nextDelNode;
nextDelNode.prev= prevDelNode;
size--;
}
//遍历链表中元素
public void view(){
System.out.print("当前链表中元素为：");
for(int i = 0;i < size;i++){
System.out.print(this.get(i)+ " ");
}
System.out.println();
}
public static void main(String[] args) {
DoubleLinkList<String> doubleLinkList =new DoubleLinkList<>();
doubleLinkList.add("hello");
doubleLinkList.add("world");
doubleLinkList.insert("test",1);
doubleLinkList.addAtHeader("first");
doubleLinkList.view();
System.out.println("索引为0处的元素值为："+ doubleLinkList.get(0));
System.out.println("test字符串在链表中索引号为：" + doubleLinkList.locate("test"));
doubleLinkList.delete(1);
System.out.print("删除索引号为1元素后，");
doubleLinkList.view();
}
}
注：本文部分内容参考自《疯狂Java程序员的基本修养》和《数据结构(C语言版)》