【数据结构】实现单链表的增删查

1.定义接口

public interface SeqList<E>{//默认尾插void add(E element);// 在线性表中插入新元素，插入后的元素下标为indexvoid add(int index,E element);//头插public void addFirst(E val);// 删除当前线性表中索引为index的元素，返回删除的元素值E removeByIndex(int index);// 删除当前线性表中第一个值为element的元素void removeByValue(E element);// 删除当前线性表中所有值为element的元素void removeAllValue(E element);// 将当前线性表中index位置的元素替换为element，返回替换前的元素值E set(int index,E element);//返回索引位index的元素E get(int index);//查询是否包含element元素boolean contains(E element);
}

2.无头单链表实现接口

链表类和节点类的定义：

public class SingleLinkedList<E> implements SeqList<E>{private Node head ;//第一节车厢的地址private int size;//车厢节点的个数，保存的元素个数//定义一个车厢类，车厢作为火车的私有内部类，对外部完全隐藏private class Node{E val;//保存的元素Node next;//下一节车厢的地址//构造方法Node(E val){this.val=val;}}}

2.1 头插addFirst

public void addFirst(E val){Node node=new Node(val);node.next=head;node=head;size++;
}

图解：

2.2 尾插add

从中间位置插入：

	@Overridepublic void add(int index, E element) {if(index<0||index>size){throw new IllegalArgumentException("add index ILLegal");}//判断没有前驱的情况if(index==0){addFirst(element);return;}//中间位置插入Node prey=head;for(int i=0;i<index-1;i++){prey=prey.next;}Node node=new Node(element);node.next=prey.next;prey.next=node;size++;}

图解：假定index=2

尾插：

    @Overridepublic void add(E element) {add(size,element);}

2.3 删除元素remove

删除当前线性表中索引为index的元素，返回删除的元素值：

    @Overridepublic E removeByIndex(int index) {if(rangeCheck(index)){throw new IllegalArgumentException("remove index Illegal");}//头节点的删除if(index==0){Node node=head;head=head.next;node.next=null;size--;return node.val;}//中间位置删除Node prey=head;for(int i=0;i<index-1;i++){prey=prey.next;}Node node=prey.next;prey.next=node.next;node.next=null;size--;return node.val;}

图解：

删除当前线性表中第一个值为element的元素：

    @Overridepublic void removeByValue(E element) {//1.base caseif(head==null){return;}//2.判断头节点恰好是待删除的节点if(head.val.equals(element)){head=head.next;size--;return;}//3.此时头节点不为空其一定不是待删除的节点Node prey=head;while(prey.next!=null){if(prey.next.equals(element)){prey.next=prey.next.next;size--;return;}prey=prey.next;}//4.当前链表不存在值为element的元素System.out.println("当前链表不存在值为"+element+"的元素");}

删除当前线性表中所有值为element的元素：

    @Overridepublic void removeAllValue(E element) {//1.base caseif(head==null){return;}//2.若头节点就是待删除的节点且出现连续的待删除的节点while(head!=null && head.val.equals(element)){head=head.next;size--;}//整个链表已经删完了if(head==null){return;}//3.头节点一定不是待删除的元素且链表不为空Node prey=head;while(prey.next!=null){if(prey.next.val.equals(element)){prey.next=prey.next.next;size--;}else{//只有后继节点不是待删除的节点才能移动Prey的引用prey=prey.next;}}}

2.4 修改元素set

将当前线性表中index位置的元素替换为element，返回替换前的元素值：

    // 将当前线性表中index位置的元素替换为element，返回替换前的元素值@Overridepublic E set(int index, E element) {if(!rangeCheck(index)){throw new IllegalArgumentException("set index illegal");}Node x=head;//遍历，走到index对应的元素for (int i = 0; i < index; i++) {x=x.next;}E oldVal=x.val;x.val=element;return oldVal;}//合法性校验private boolean rangeCheck(int index){if(index<0||index>=size){return false;}return true;}

2.5 获取元素get

返回索引为index的元素：

    @Overridepublic E get(int index) {if(!rangeCheck(index)){throw new IllegalArgumentException("get index illegal");}Node x=head;for(int i=0;i<index;i++){x=x.next;}return x.val;}

3.带头单链表实现接口

由于单链表中都需要额外处理头结点的情况，引入一个虚拟头结点，这个节点不存在具体的值，就作为链表的头来使用，使每个有值的节点都有一个前驱。（所有操作都统一了，无论是插入还是删除，都可以看作是中间位置的插入和删除）

链表类和节点类的定义：

public class SingleLinkedListWithHead <E> implements SeqList<E>{//当前链表一定存在火车头且不存储任何元素private Node dummyHead=new Node(null);//具体的元素个数private int size;private class Node{E val;Node next;Node(E val){this.val=val;}}
}

3.1 头插addFirst

    public void addFirst(E val){Node node=new Node(val);node.next=dummyHead.next;dummyHead.next=node;size++;}

图解：

3.2 尾插add

    @Overridepublic void add(E element) {add(size,element);return;}@Overridepublic void add(int index, E element) {if(index<0||index>size){throw new IllegalArgumentException("Remove index illegal");}Node prey=dummyHead;for(int i=0;i<index;i++){prey=prey.next;}Node node=new Node(element);node.next=prey.next;prey.next=node;size++;}

3.3 删除元素remove

    @Overridepublic void removeAllValue(E element) {//prey一定指向不是待删除的节点Node prev=dummyHead;while(prev.next!=null){if(prev.next.val==element){prev.next=prev.next.next;size--;}else{prev=prev.next;}}}

3.4 判断是否包含元素element

    @Overridepublic boolean contains(E element) {while(dummyHead.next!=null){if(dummyHead.next.val.equals(element)){return true;}dummyHead.next=dummyHead.next.next;}return false;}