Java有关链表的基本操作-526互联

上一篇发表的数组的基本操作,但是数组有优势也有劣势:

·具体的优势是:拥有高效的随机访问能力

·劣势是:由于排列紧密相连，插入和删除元素都会导致大量元素被迫移动，影响效率。

接下来要阐述的数据结构是链表:

·先看看单向链表的结构:

单向链表的每一个节点又包含两个部分，一部分是存放数据的变量data，另一部分是指向下一节点的指针next。

private static class Node{
        int data;
        Node next;
    }

再看看双向链表:

·如果说数组在内存中的存储方式是顺序存储，那链表在内存中的存储方式是随机存储，
链表的每一个节点分布在不同的位置上，依靠next指针练习起来。

进入正题:链表的基本操作！

1.查找节点:
查找元素时，链表只能从头节点开始向后一个一个节点逐一查找
第一步:将查找的指针定位到头节点;
第二步:根据头节点的next指针,定位到第2个节点;
第三步:以此类推。

public Node get(int index) throws Exception{
        if(index<0||index>=size){
            throw new IndexOutOfBoundsException("访问越界!!!");
        }
        //将查找的指针定位到头节点
        Node temp=head;
        for(int i=0;i<index;i++){
            temp=temp.next;
        }
        return temp;
    }

2.更新节点:
链表的更新过程与数组类似，直接将旧数据替换成新数据即可。

public void updateNode(int data,int index) throws Exception{
        if(index<0||index>size){
            throw new IndexOutOfBoundsException("访问越界!!!");
        }
        Node temp=head;
        for(int i=0;i<index;i++){
            temp=temp.next;
        }
        temp.data=data;
    }

3.插入节点:
与数组类似,链表插入节点时，同样分为三种情况:
尾部插入:

把最后一个节点的next指针指向新插入的节点即可。

头部插入:

大致分为两步
第一步:将新节点的next指针指向原先的头节点;
第二步:将新节点变成链表的头节点。

中间插入:

分为两步
第一步:新节点的next指针，指向插入位置的节点;
第二部:插入位置前置节点的next指针，指向新节点。

public void insert(int data,int index) throws Exception{
        //判断是否访问越界
        if(index<0||index>size){
            throw new IndexOutOfBoundsException("访问链表越界!!!");
        }
        //创建一个节点
        Node insertdNode=new Node(data);
        if(size==0){
            //空链表
            head=insertdNode;
            last=insertdNode;
        }else if(index==0){
            //插入头部
            insertdNode.next=head;
            head=insertdNode;
        }else if(index==size){
            //插入尾部
            last.next=insertdNode;
            last=insertdNode;
        }else{
            //插入中间
            Node preNode=get(index-1);//插入位置的前置节点
            insertdNode.next=preNode.next;
            preNode.next=insertdNode;
        }
        size++;
    }

4.删除节点:
分为三种情况

```
     尾部删除:
```

     将倒数第二个节点的next指针指向空即可。

```
     头部删除:
```

     将链表的头节点设为原先头节点的next指针即可。

```
     中间删除:
```

     将要删除的节点的前置节点的next指针指向要删除节点的下一个节点即可。

public Node remove(int index) throws Exception{
        //判断是否访问越界
        if(index<0||index>=size){
            throw new IndexOutOfBoundsException("访问越界!!!");
        }
        //初始化删除节点
        Node removedNode=null;
        if(index==0){
            //删除头节点
            removedNode=head;
            head=head.next;
        }else if(index==size){
            //删除尾节点
            Node preNode=get(index-1);
            removedNode=preNode.next;
            preNode.next=null;
            last=preNode;
        }else{
            //删除中间节点
            Node preNode=get(index-1);//要删除节点的前置节点
            removedNode=preNode.next;
            preNode.next=preNode.next.next;
        }
        size--;
        return removedNode;
    }

5.链表基本操作的完整代码:

点击查看代码

package LiknList;

public class MyLinkList {
    //链表节点
    private static class Node{
        int data;
        Node next;
        Node(int data){
            this.data=data;
        }
    }
    //头节点指针
    private Node head;
    //尾部节点
    private Node last;
    //链表实际长度
    private int size;

    //链表插入元素(int data:要插入的元素,int index:要插入的位置)
    public void insert(int data,int index) throws Exception{
        //判断是否访问越界
        if(index<0||index>size){
            throw new IndexOutOfBoundsException("访问链表越界!!!");
        }
        //创建一个节点
        Node insertdNode=new Node(data);
        if(size==0){
            //空链表
            head=insertdNode;
            last=insertdNode;
        }else if(index==0){
            //插入头部
            insertdNode.next=head;
            head=insertdNode;
        }else if(index==size){
            //插入尾部
            last.next=insertdNode;
            last=insertdNode;
        }else{
            //插入中间
            Node preNode=get(index-1);//插入位置的前置节点
            insertdNode.next=preNode.next;
            preNode.next=insertdNode;
        }
        size++;
    }

    //链表删除元素(index:删除的位置)
    public Node remove(int index) throws Exception{
        //判断是否访问越界
        if(index<0||index>=size){
            throw new IndexOutOfBoundsException("访问越界!!!");
        }
        //初始化删除节点
        Node removedNode=null;
        if(index==0){
            //删除头节点
            removedNode=head;
            head=head.next;
        }else if(index==size){
            //删除尾节点
            Node preNode=get(index-1);
            removedNode=preNode.next;
            preNode.next=null;
            last=preNode;
        }else{
            //删除中间节点
            Node preNode=get(index-1);//要删除节点的前置节点
            removedNode=preNode.next;
            preNode.next=preNode.next.next;
        }
        size--;
        return removedNode;
    }

    //链表查找元素(index:查找的位置)
    public Node get(int index) throws Exception{
        if(index<0||index>=size){
            throw new IndexOutOfBoundsException("访问越界!!!");
        }
        //将查找的指针定位到头节点
        Node temp=head;
        for(int i=0;i<index;i++){
            temp=temp.next;
        }
        return temp;
    }

    //更新节点(data:更新的数据,index:更新的位置)
    public void updateNode(int data,int index) throws Exception{
        if(index<0||index>size){
            throw new IndexOutOfBoundsException("访问越界!!!");
        }
        Node temp=head;
        for(int i=0;i<index;i++){
            temp=temp.next;
        }
        temp.data=data;
    }

    //输出链表
    public void output(){
        Node temp=head;
        while(temp!=null){
            System.out.print(temp.data+" ");
            temp=temp.next;
        }
    }

    public static void main(String[] args) throws Exception {
        MyLinkList myLinkList=new MyLinkList();
        myLinkList.insert(3,0);
        myLinkList.insert(7,1);
        myLinkList.insert(9,2);
        myLinkList.insert(5,3);
        myLinkList.insert(6,1);
        myLinkList.remove(0);
        myLinkList.updateNode(4,1);
        myLinkList.output();
    }
}

6.数组和链表的好与坏:
数组:查找和更新都是O(1),插入和删除是O(n);
链表:查找是O(n),其余都是O(1)。

基本操作elasticsearch java api