java实现链表的增删改查

java实现链表的增删改查 1.链表的增加 1.1 链表头部增加addFirst(int val)

• 先创建节点 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;

2.1 get(int index)

先判断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;
        }
    }