java实现链式线性表

package ch9;

public class LinkList <T>{

private class Node
{
//保存节点的数据
private T data;
//指向下一个节点的引用
private Node next;
public Node(T data,Node next)
{
this.data = data;
this.next = next;
}
}
//保存该链表的头节点
private Node header;
//保存该链表的尾节点
private Node tail;
//保存该链表已有的节点数
private int size;
//创建空链表
public LinkList()
{
header =null;
tail = null;
}
//以指定元素来创建链表，该链表只有一个元素
public LinkList(T element)
{
header = new Node(element, null);
tail =header;
size++;
}
//返回链表的长度
public int length()
{
return size;
}
//获取链表索引为index处的元素
public T get(int index)
{
return getNodeByIndex(index).data;
}

private Node getNodeByIndex(int index)
{
if(index<0 || index>size-1)
throw new IndexOutOfBoundsException("线性表索引越界");
Node current = header;
for(int i=0;i<size &&current!=null;i++,current=current.next)
{
if(i==index)
return current;
}
return null;
}

// 查找执行元素的位置
public int locate(T element){
Node current = header;
for(int i=0;i<size && current!=null;i++,current=current.next)
{
if(current.data.equals(element))
return i;
}
return -1;
}
//向指定位置插入一个元素
public void insert(int index,T element)
{
if(index<0 || index>size)
throw new IndexOutOfBoundsException("索引越界");
//如果是空链表
if(header == null)
{
add(element);
}
else{
if(index ==0)
{
addAtHeader(element);
}
else{
Node prev = getNodeByIndex(index-1);

prev.next =new Node(element,prev.next);
// prev.next =prev.next.next;
//prev.next.data =element;

}
}
}
//头部插入节点
private void addAtHeader(T element) {
// TODO Auto-generated method stub
header = new Node(element,header);
if(tail ==null){
tail =header;
}
size ++;
}
//尾部插入
public void add(T element) {
// TODO Auto-generated method stub
if(header ==null)
{
header = new Node(element,null);
tail =header;
}
else{
Node newNode = new Node(element,null);
tail.next =newNode;
}
size++;
}
}

巴特西

java实现链式线性表

最新文章

热门文章