package cn.com.factroy2;
/**
* 可以看做是操作链表的工具类，链表的核心结构就是节点的数据结构
* @author wanjn
*
*/
public class SinglyLinkedList {
//存放头结点
private Node head;
//存放尾节点
private Node last;
//链表长度
private int size = 0;
/**
* 默认在最后添加元素
* @param data
*/
public void add(Object data){
addLastNode(data);
}
/**
* 向链表中添加头节点
* @param data
*/
public void addFirstNode(Object data){
if (head==null) {//添加的第一个节点作为头结点
head = new Node(data, null);
last = head;
}else {//不是头结点，将新的节点作为头结点
head = new Node(data, head);
}
size++;
}
/**
* 清空链表
*/
public void clear() {
int length = length();
for (int i = 0; i < length; i++) {
delete(0);
}
}
/**
* 向链表中添加尾部节点
* @param data
*/
public void addLastNode(Object data){
//head 要保持不变
if (head==null) {//这里可以使用新增一个辅助节点的监督元思想，去掉一个判断，减少执行判断的时间；当然啦最后需要将监督元删除即可
head = new Node(data, null);
last = head;
}else {
last.next=new Node(data, null);
last = last.next;
}
size++;
}
/**
* 获得链表的长度
* @return 长度
*/
public int length(){
return size;
}
/**
* 根据索引设置对应节点的值
* @param index
* @param data
*/
public void set(int index,Object data){
getNode(index).data=data;
}
/**
* 根据索引删除对应的节点
* @param index
*/
public void delete(int index){
Node current = getNode(index);
//删除头结点
if (index==0) {
if (size==1) {
head = null;
}else {
head = getNode(index+1);
}
}else if (index == size-1) {
//删除尾节点
last =getNode(index-1);
getNode(index-1).next=null;
}else {
//删除非头结点和尾节点
Node pre = getNode(index-1);
Node next = getNode(index+1);
pre.next = next;
}
//这个必须放在后面，不能放在开始，否则会影响（找不到）下一个节点的查找
current.next = null;
size--;
}
/**
* 根据索引获取链表对应节点的值
* @param index
* @return
*/
public Object get(int index){
return getNode(index).data;
}
@Override
public String toString() {
String result="";
Node temp = head;
if (temp!=null) {
while (temp!=null) {
result+= temp.data+ ", ";
temp = temp.next;
}
result = result.substring(0,result.lastIndexOf(", ")) ;
}
return "["+result+"]" ;
}
/**
* 根据索引获取链表对应节点
* @param index
* @return
*/
private Node getNode(int index){
if (index<0||index>=size) {
throw new RuntimeException("索引超出范围！");
}
Node temp = head;
for (int i = 0; i <size; i++) {
if (i==index) {
break;
}
temp = temp.next;
}
return temp;
}
/**
* 将节点的关系操作封装在了node的构造方法中
* @author
*
*/
private class Node {
public Object data;
public Node next;
public Node(Object data, Node next) {
super();
this.data = data;
this.next = next;
}
}
}
