单链表

/**

* 定义列表的接口,所有列表该实现的约定

* 增删改查

* @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;

}

}