/**
* 定义列表的接口,所有列表该实现的约定
* 增删改查
* @author Administrator
*
*/
public interface MyList {
/**
* 增加一个元素
* @param element
*/
void add(Object element);
/**
* 根据值，删除一个元素
* @param element
*/
void delete(Object element);
/**
* 根据下标删除一个元素
* @param index
*/
void delete(int index);
/**
* 根据下标更新一个元素
* @param index
* @param element
*/
void update(int index, Object element);
/**
* 判断线性表中是否包含该元素
* 返回布尔型
* @param element
* @return
*/
boolean contains(Object element);
/**
* 返回线性表中与该元素相等的值的下标
* 如果没有返回-1
* @param element
* @return
*/
int index(Object element);
}
public class _02SinagleLinkedList implements MyList{
ListNode first;
ListNode last;//队尾指针
int size = 0;//单链表当前存储容量
@Override
public String toString() {
StringBuilder sb = new StringBuilder("[");
ListNode p = first;
while(p != null) {
if(p.next != null)
sb.append(p.data + " , ");
else
sb.append(p.data);
p = p.next;
}
sb.append("]");
return sb.toString();
}
@Override
public void add(Object element) {
if(first == null) {
first = new ListNode(element);
last = first;
}else {
last.next = new ListNode(element);
last = last.next;//每次更新尾指针
}
size++;
}
@Override
public void delete(Object element) {
ListNode p = first;
ListNode pre = null;
while(p != null) {
if(p.data.equals(element)) {//找到要删除的节点
if(p == first)
first = first.next;//删掉头结点
else
pre.next = p.next;//跨过当前节点
break;//只删除第一个与值相同的元素
}
pre = p;//每次记录当前节点的前一个节点
p = p.next;
}
size--;
}
@Override
public void delete(int index) {//按索引进行删除
if(index >= size||index < 0) {
//System.out.println("错误");
return;
}
ListNode p = first;
ListNode pre = null;
int i = 0;
while(p != null) {
if(i == index) {
if(p == first)
first = first.next;
else
pre.next = p.next;
break;
}
i++;//索引随节点向下更新
pre = p;
p = p.next;
}
size--;
}
@Override
public void update(int index, Object element) {
if(index >= size||index < 0)
return;
ListNode p = first;
int i = 0;
while(p != null) {
if(i == index) {
p.data = element;
break;
}
p = p.next;
i++;
}
}
@Override
public boolean contains(Object element) {
ListNode p = first;
while(p != null) {
if(p.data.equals(element))
return true;
p = p.next;
}
return false;
}
@Override
public int index(Object element) {
ListNode p = first;
int i = 0;
while(p != null) {
if(p.data.equals(element))
return i;
p = p.next;
i++;
}
return -1;
}
}
