单链表的简介与实现(Java)

妖狐艹你老母 2023-10-12 22:46 18阅读 0赞

## 一、前言 ##

线性结构的链式存储是用若干地址分散的存储单元存储数据元素，逻辑上相邻的两个数据元素在物理位置上并不一定相邻，必须采用附加信息来表示数据元素之间的顺序关系。因此存储一个数据元素的数据单元至少包含两部分------数据域和地址域

![4306c61a1c2a4cf3a4aeaa81e9b6b073.png][]

上述的结构通常称为结点

一个节点表示一个数据元素，通常节点当中的地址会把数据结点连接起来，节点当中的连接关系体现了线性表当中数据元素间的顺序关系，采用这种关系的称为**线性链表**。

![755f8a3e35a34f3cb523574299b24891.png][]

从上图当中，head是线性链表当中的第一个节点，但是这个节点在数据域当中并没有存储数据，这里之所以写这个的目的是我们能够通过头指针去遍历我们整个链表。

最后一个节点的地址域为空，表示其后不再有节点。每个结点只有一个地址域的链表称为单链表

**单链表**：该地址域通常指向候机节点； 每个节点有两个地址域的线性表称为双链表

**双链表**：两个地址域分别指向前驱节点和后继节点。

![d345196338064f2a9af95b3857d15fbf.png][]

## 二、单链表的实现 ##

### 定义单链表的节点 ###

value表示当前节点的值，next表示指向下个节点的地址

public class ListNode {
    
        int value;
        ListNode next;
    
        public ListNode(int value){
            this.value = value;
        }
    }

### 头插法和尾插法 ###

创建一个链表类，定义头节点

public class LinkList {
    
        ListNode head = null;
    }

#### 头插法 ####

public  void HeadInsert(int val) {
    		//每次执行这个方法的时候，都要新建路一个节点用来存储数据、
    		ListNode listNode = new ListNode(val);
    		//判断头特点是否为空,如果是那么将头结点指向新的节点，然后结束
    		if (head == null) {
    			head = listNode;
    			return;
    		}
    		
    		listNode.next = head;
    		head= listNode;
    	}

#### 尾插法 ####

public  void EndInsert(int val) {
    		//每次执行这个方法的时候，都要新建路一个节点用来存储数据、
    		ListNode listNode = new ListNode(val);
    		//判断头特点是否为空,如果是那么将头结点指向新的节点，然后结束
    		if (head == null) {
    			head = listNode;
    			return;
    		}
    		
    		//定义一个临时结点由他的充当指针，指针最开始指向头节点
    		ListNode indexNode = listNode;
    		//从头结点可是遍历，到最尾部插入
    		while (indexNode.next != null) {
    			indexNode = indexNode.next;
    			
    		}
    		indexNode.next = listNode;
    	}

### 遍历链表 ###

#### 输出链表每个节点的值 ####

public void printLink() {
    		//定义一个临时结点充当指针，从头结点喀什不断想向后移动
    		ListNode tempListNode = head;
    		
    		//将临时结点不断的往后边移动，直到临时结点指向了 null;
    		while (tempListNode  !=null) {
    			System.out.print(tempListNode.val);
    			tempListNode = tempListNode.next;
    		}
    		System.out.println();
    	}

#### 输出链表长度 ####

public int getLenght() {
    		//定义一个节点指向该链表
    		ListNode tempListNode = head;
    		int length = 0;
    		while (tempListNode != null) {
    			length ++;
    			tempListNode = tempListNode.next;
    		}
    		
    		return length;
    	}

### 链表反转 ###

假设我们准备1-》2-》3-》4

> 准备两个空结点 pre用来保存先前结点、next用来做临时变量
> 
> 在头结点node遍历的时候此时为1结点
> 
> next = 1结点.next(2结点)
> 
> 1结点.next=pre(null)
> 
> pre = 1结点
> 
> node = 2结点
> 
> 进行下一次循环node=2结点
> 
> next = 2结点.next(3结点)
> 
> 2结点.next=pre(1结点)=>即完成2->1
> 
> pre = 2结点
> 
> node = 3结点
> 
> 进行循环…

public void reverseList(LinkList list){
            ListNode pre = null;
            ListNode next = null;
            while (list.head != null){
                next = head.next;
                head.next = pre;
                pre = head;
                head = next;
            }
            head = pre;
        }

### 判断链表是否成环 ###

如果一个链表中有环，也就是说用一个指针去遍历，是永远走不到头的。因此，我们可以用两个指针去遍历，一个指针一次走两步， 一个指针一次走一步，如果有环，两个指针肯定会在环中相遇。时间复杂度为O(n)。

public boolean ring(LinkList list){
            ListNode fastNode = list.head;
            ListNode slowNode = list.head;
            while (fastNode != null && fastNode.next != null){
                fastNode = fastNode.next.next;
                slowNode = slowNode.next;
                if (fastNode == slowNode){
                    return true;
                }
            }
            return false;
        }

### 获取链表的后K个节点 ###

使用两个指针，先让前面的指针走到正向第k个结点，这样前后两个指针的距离差是k-1， 之后前后两个指针一起向前走，前面的指针走到最后一个结点时，后面指针所指就是后K个结点

public void kList(LinkList list,int k){
            if (k > list.getLength(list)) throw new RuntimeException("k值超出链表长度");
            ListNode aHead = list.head;
            ListNode bHead = list.head;
            while (aHead != null && k >= 1){
                aHead = aHead.next;
                k--;
            }
            while (aHead != null){
                aHead = aHead.next;
                bHead = bHead.next;
            }
            list.head = bHead;
        }

## 三、测试 ##

写一个测试类

public class LinkTest {
        public static void main(String[] args) {
            LinkList list1 = new LinkList();
            list1.endInsert(1);
            list1.endInsert(2);
            list1.headInsert(0);
            System.out.println(list1.getLength(list1));
            list1.printLink(list1);
            System.out.println("reverseList");
            list1.reverseList(list1);
            list1.printLink(list1);
            list1.kList(list1,2);
            System.out.println(list1.ring(list1));
        }
    }

运行测试

![fcffade963664db2bbbd1a09c1f5ce73.png][]

代码已同步至Gitee：[LinkAhieve: 单链表实现][LinkAhieve_]

[4306c61a1c2a4cf3a4aeaa81e9b6b073.png]: https://img-blog.csdnimg.cn/4306c61a1c2a4cf3a4aeaa81e9b6b073.png
[755f8a3e35a34f3cb523574299b24891.png]: https://img-blog.csdnimg.cn/755f8a3e35a34f3cb523574299b24891.png
[d345196338064f2a9af95b3857d15fbf.png]: https://img-blog.csdnimg.cn/d345196338064f2a9af95b3857d15fbf.png
[fcffade963664db2bbbd1a09c1f5ce73.png]: https://img-blog.csdnimg.cn/fcffade963664db2bbbd1a09c1f5ce73.png
[LinkAhieve_]: https://gitee.com/kan-peizhen_admin_admin/link-ahieve.git