hi,上一期已经给大家分享过代码版的链表的增删查改了,现在要对部分方法进行详细的介绍了
首先来说一说在任意位置的增加一个结点
废话不多说,开整
先来一幅图
加入已经有这样的链表了,现在要在 任意一个位置插入元素
我们先考虑一下
1.如果是在0下标插入,那么就直接调用头插法
2.如果在3下标插入,直接调用尾插法
3.在中间的位置插入
1.2比较简单,就不重复了
假如要在2下标插入一个结点,那就是要找2位置的前一个结点
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index, int data)
要先判定index位置是否合法
private void isValid(int index) throws IndexOutOfException{ if(index<0||index>size()){ throw new IndexOutOfException("index位置不合法"); } }
然后要找到index-1位置的结点
private Node findPlace(int index){ Node cur=head; int count=0; while(count!=index-1){ count++; cur=cur.next; } return cur; }
然后我们看那个图,就是用node.next=cur.next,然后cur.next=node就完成了插入的操作
public void addIndex(int index, int data){ Node node=new Node(data); Node cur=findPlace(index); node.next=cur.next; cur.next=node; }
这个就写完了
下面再来说一说这个删除值为key的结点的方法
现在要删除值为27的结点,
这个图说明要找到要删除结点的前一个结点
private Node searchPlace(int key){ Node cur=head; while(cur.next!=null){ if(cur.next.val==key){ return cur; } cur=cur.next; } return null; }
然后是删除操作的实现
//删除第一次出现关键字为key的节点 public void remove(int key){ if(head==null){ return; } if(head.val==key){ head=head.next; return; } Node cur=searchPlace(key); Node del=cur.next; cur.next=del.next; }
如果是删除最后一个结点,也是上述做法
最后一个
//删除所有值为key的节点
public void removeAllKey(int key)
这个是最复杂的
上图
public void removeAllKey(int key) { if (head == null) { return; } Node prev = head; Node cur = head.next; while (cur != null) { if (cur.val == key) { prev.next = cur.next; cur = cur.next; } else { prev = cur; cur = cur.next; } } if(head.val==key){ head=head.next; } }
今天的讲解就到这里了,我们下期再见了,886!!!