单链表的基本操作（Java实现）

分手后的思念是犯贱 2024-04-18 12:41 65阅读 0赞

## 单链表的基本操作（Java实现） ##

#### 1.单链表简介： ####

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。  
链表中的数据是**以结点**来表示的，每个结点的**构成**：**元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。**  
以“结点的序列”表示线性表称作线性链表（单链表），单链表是链式存取的结构。

#### 2.单链表的一些特征总结： ####

利用Java实现一个简单的单链表存储结构，即结点，可以用以下语句来实现：

public class LinkedList {
        public int data;			//数据域，存放结点的数据
        public LinkedList next;		//指针域,指向下一个结点
        public LinkedList(int data){
           this.data=data;
        }
    }

由于单链表存储结构的特点，整个链表的存取必须从头指针开始进行。  
假设链表为 a 1 → a 2 → a 3 → a 4 → a 5 a\_\{1\}\\rightarrow a\_\{2\}\\rightarrow a\_\{3\}\\rightarrow a\_\{4\}\\rightarrow a\_\{5\} a1→a2→a3→a4→a5，先创建一个头结点对象：`LinkedList head=new LinkedList(0);`，让头结点的指针域指向链表的第一个结点，则有`head.next=a1;`；  
如果`head.next==null`，也就是头结点的下一个结点为空，很显然就是链表为空；  
假设一个指针temp指向了链表的最后一个结点，即`temp=a5`时，显然 a 5 a\_\{5\} a5后面已经没有元素了，那么就可以用`temp.next=null;`来表示链表为空的情况。

#### 3.方法代码实现 ####

##### 3.1判断链表是否为空 #####

/**
     * 判断链表是否为空
     */
        public boolean isEmpty(){
            boolean flag=false;		//假定链表不为空
            if (head.next==null){
                flag=true;			//头结点的next如果为null，说明链表中不含有其他元素，故链表为空，置flag为true
            }
            return flag;		//返回flag，可用于后续方法
        }

##### 3.2往链表尾部添加结点 #####

思路：先定义一个辅助指针temp，遍历链表，让辅助指针指向链表的最后一个结点，然后让temp.next指向要添加进链表的结点。

/**
         * 往链表尾部添加新结点
         * @param element 要添加进链表的结点
         */
        public void add(LinkedList element){
            //因为头结点head不能动，所以建立一个临时结点temp来作为辅助
            LinkedList temp=head;
            //遍历当前链表，找到最后一个结点
            while (true){
                if (temp.next==null){//temp若为链表尾部的结点，故temp.next为null时，就是链表的最后一个结点了
                    break;
                }
                temp=temp.next;//让temp指向temp.next，也就是让temp结点后移了,从而实现遍历
            }
            //当循环退出后，temp就指向了当前链表的最后一个元素，修改temp的next域，让其指向新的节点即可。
            temp.next=element;
        }

##### 3.3遍历链表，并输出每个结点的数据域 #####

思路：先定义一个辅助指针temp，然后写一个whlie循环，利用temp=temp.next语句来遍历链表，每遍历到一个结点就输出其数据域的值到控制台，当辅助指针指向链表的最后一个结点的下一个位置时，退出循环。

/**
         * 遍历链表
         */
        public void showList(){
            if (isEmpty()){
                System.out.println("链表为空");
                return;
            }
            //如果链表不为空,遍历链表并打印
            LinkedList temp=head;
            while (true){
                if (temp==null){//当temp指向链表中最后一个结点的next时，遍历结束，输出提示信息，跳出循环
                    System.out.println("遍历结束");
                    break;
                }
                if (temp.next!=null){//temp一开始指向头结点，但头结点不应属于链表内，故从temp.next.data开始打印
                    System.out.printf("%d ",temp.next.data);
                }
                temp=temp.next;//把temp.next赋给temp,实现遍历
            }
        }