Java单向链表详解(定义使用及实现示例)

单向链表的定义

单向链表是链表的一种，其特点是链表的链接方向是单向的，或叫单链表。

单向链表的数据结构主要包含两个：

1. 一个数据域：存储数据；
2. 一个指针域：用于指向下一个节点；

而最后一个节点则指向一个空值，具体如下图所示：

 

单向链表的特点

1）利用单链表可以解决顺序表需要大量连续存储空间的缺点；

2）结点的删除、插入非常方便，不需要像线性结构那样移动剩下的数据；

3）结点的访问方便，可以通过循环或者递归的方法访问到任意数据，但是平均的访问效率低于线性表；

4）查找某个特定结点时，需要从头开始遍历。

 

Java单向链表的实现

下面我通过实现一个Java单向链表，这样大家可以更好的理解Java单向链表的操作使用。

主要分为如下5个操作：

1.建立单向链表的节点

public class Node {

    private Object data;

    private Node next;

    public Node() {
    }

    public Node(Object data) {
        this.data = data;
    }

    public Node(Object data, Node next) {
        this.data = data;
        this.next = next;
    }

    public Object getData() {
        return data;
    }

    public void setData(Object data) {
        this.data = data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

 

2.添加元素

/**
     * 链尾添加
     * @param value
     */
    public void addData(Object value){
        Node newNode = new Node(value);

        Node temp = head;

        while (temp.next != null){
            temp = temp.next;
        }

        temp.next = newNode;
        size ++;
    }

 

3.插入元素

/**
    * 在指定位置插入
    * @param index
    * @param value
    */
   public void insertData(int index, Object value){
       if(index < 0 || index > size ){
           System.out.println("插入位置不合法");
           return;
       }

       int curPos = 0; //当前位置
       Node temp = head; //临时节点
       Node insertNode = new Node(value);//插入的新节点

       while (temp != null){

           if(curPos == index){
               insertNode.next = temp.next;
               temp.next = insertNode;

               size ++;
               return;
           }

           temp = temp.next;
           curPos ++;
       }
   }

 

4.删除元素

/**
 * 删除指定位置的节点
 * @param index
 */
public void deleteData(int index){
    if(index < 0 || index > size ){
        System.out.println("插入位置不合法");
        return;
    }

    int curPos = 0; //当前位置
    Node temp = head; //临时节点

    while (temp != null){

        if(curPos == index){
            Node deleteNode = temp.next;
            temp.next = deleteNode.next;

            size --;
            return ;
        }

        temp = temp.next;
        curPos ++ ;
    }
}

 

5.遍历元素

 /**
 * 遍历链表
 */
public void traverse(){
    Node temp = head.next;

    System.out.println(" size = "+size);

    while (temp != null){

        System.out.println(" "+temp.data);

        temp = temp.next;
    }
}

 

陈睿mikechen

10年+大厂架构经验，资深技术专家，就职于阿里巴巴、淘宝、百度等一线互联网大厂。

关注「mikechen」公众号，获取更多技术干货！

后台回复【面试】即可获取《史上最全阿里Java面试题总结》，后台回复【架构】，即可获取《阿里架构师进阶专题全部合集》