- 先创建节点 Node node = new node(val);
- 判断头部是否为空,若为空,head=node;头部不为空,让新建的节点指向头部,node.next=head;头指针再指向新建节点head=node;
注意:如果不清除指向的先后顺序,可以画图帮助判断。如若各种指向顺序都不行,建立临时变量
public void addFirst(int val){ // 先创建需要挂载的车厢节点 Node node =new Node(val); // 判断火车头部是否为空 if (head==null){ head=node; } // 火车有节点,要将当前新车厢挂载到火车头节点上 else{ // 新车厢指向head头节点 node.next=head; // 新的头节点再指向之前的头节点 head=node; } size++; }1.2 链表中间位置插入addIndex(int index,int val)
- 首先判断索引的合法性(index<0 || index>size)非法
- 若index=0为头部插入
- index在中间位置(核心是找到插入位置的前驱节点)
例如将7插入到index为1的位置,先让7指向插入位置,再让它的前驱节点指向它。
前驱节点怎样找?
用for循环遍历找到prev位置
public void addIndex(int index,int val){ // 判断合法性 if (index<0 || index>size){ System.out.println("error"); return; } if (index==0){ addFirst(val); return; } // 插入元素,先创建 Node node =new Node(val); // 找插入位置的前驱节点,先让前驱节点为头节点,在遍历向后走index-1步 Node prev=head; for (int i = 0; i < index-1; i++) { prev=prev.next; } node.next=prev.next; prev.next=node; size++; }2.链表的查找
- get(int index)返回index位置的元素值
- contains(int value) 查询值为value的元素在单链表中是否存在,存在返回true,否则返回false;
先判断index合法性(index<0 || index>=size)非法,此处index不能=size,因为size位置无元素
public int get(int index){ // 合法性校验 rangecheck(index)为index合法性检测的方法 if (rangecheck(index)){ Node node=head; // 规定了node节点走了多少步 for (int i = 0; i < index; i++) { node=node.next; } return node.val; }else{ System.out.println("error"); return -1; } }2.2 contains(int value)
public boolean contains(int val){ Node temp=head; while(temp!=null){ if (temp.val==val){ return true; } temp=temp.next; } return false; }3.链表的修改set(int index,int newval)
// 修改链表index位置的元素值,返回修改前的值 public int set(int index,int newval){ if (rangecheck(index)){ Node node=head; for (int i = 0; i < index; i++) { node=node.next; } int oldval=node.val; node.val=newval; return oldval; }else{ System.out.println("error"); return -1; } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)