文档章节

自己动手写一个单链表

公众号_好好学java
 公众号_好好学java
发布于 06/20 07:24
字数 1984
阅读 582
收藏 8

文章有不当之处,欢迎指正,如果喜欢微信阅读,你也可以关注我的微信公众号:好好学java,获取优质学习资源。

一、概述

单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始。

链式存储结构的线性表将采用一组任意的存储单元存放线性表中的数据元素。由于不需要按顺序存储,链表在插入、删除数据元素时比顺序存储要快,但是在查找一个节点时则要比顺序存储要慢

使用链式存储可以克服顺序线性表需要预先知道数据大小的缺点,链表结构可以充分利用内存空间,实现灵活的内存动态管理。但是链式存储失去了数组随机存取的特点,同时增加了节点的指针域,空间开销较大。

二、图解

下图就是最简单最一般的单向链表:

这里写图片描述

新增节点:

将值为element的新节点插入到第index的位置上。

首先要先找到索引为index-1的节点,然后生成一个数据为element的新节点newNode,并令index-1处节点的next指向新节点,新节点的next指向原来index处的节点。 这里写图片描述

删除节点:

删除第index个节点,第index节点是由index-1出的节点引用的,因此删除index的节点要先获取index-1处的节点,然后让index-1出节点的next引用到原index+1处的节点,并释放index处节点即可。

这里写图片描述

三、单向链表的Java实现

下面的程序分别实现了线性表的初始化、获取线性表长度、获取指定索引处元素、根据值查找、插入、删除、清空等操作。

public class LinkList<T> {  
   
    // 定义一个内部类Node,代表链表的节点  
    private class Node {  
   
        private T data;// 保存数据  
        private Node next;// 指向下个节点的引用  
   
        // 无参构造器  
        public Node() {  
        }  
   
        // 初始化全部属性的构造器  
        public Node(T data, Node next) {  
            this.data = data;  
            this.next = next;  
        }  
    }  
   
    private Node header;// 保存头结点  
    private Node tail;// 保存尾节点  
    private int size;// 保存已含有的节点数  
   
    // 创建空链表  
    public LinkList() {  
        header = null;  
        tail = null;  
    }  
   
    // 已指定数据元素创建链表,只有一个元素  
    public LinkList(T element) {  
   
        header = new Node(element, null);  
        // 只有一个节点,header,tail都指向该节点  
        tail = header;  
        size++;  
    }  
   
    // 返回链表的长度  
    public int length() {  
        return size;  
    }  
   
    // 获取指定索引处的元素  
    public T get(int index) {  
        return this.getNodeByIndex(index).data;  
    }  
   
    //获取指定位置的节点  
    private Node getNodeByIndex(int index){  
        if(index < 0 || index > size-1){  
            throw new IndexOutOfBoundsException("索引超出线性表范围");  
        }  
           
        Node current = header;//从header开始遍历  
           
        for(int i=0; i<size && current!=null; i++,current=current.next){  
            if(i == index){  
                return current;  
            }  
        }  
           
        return null;  
    }  
       
    //按值查找所在位置  
    public int locate(T element){  
        Node current = header;  
           
        for(int i=0; i<size && current!=null; i++, current=current.next){  
            if(current.data.equals(element)){  
                return i;  
            }  
        }  
           
        return -1;  
    }  
       
    //指定位置插入元素  
    public void insert(T element, int index){  
       
        if(index < 0 || index > size){  
            throw new IndexOutOfBoundsException("索引超出线性表范围");  
        }  
           
        //如果是空链表  
        if(header == null){  
            add(element);  
        }  
        else{  
            //当index为0时,即在链表头处插入  
            if(0 == index){  
                addAtHead(element);  
            }  
            else{  
                Node prev = getNodeByIndex(index - 1);//获取前一个节点  
                //让prev的next指向新节点,新节点的next指向原来prev的下一个节点  
                prev.next = new Node(element, prev.next);  
                size++;  
            }  
        }  
    }  
   
       
    //在尾部插入元素  
    public void add(T element) {  
           
        //如果链表是空的  
        if(header == null){  
            header = new Node(element, null);  
               
            //只有一个节点,headwe,tail都该指向该节点  
            tail = header;  
        }  
        else{  
            Node newNode = new Node(element, null);//创建新节点  
            tail.next = newNode;//尾节点的next指向新节点  
            tail = newNode;//将新节点作为尾节点  
        }  
           
        size++;  
    }  
       
       
    //头部插入  
    public void addAtHead(T element){  
        //创建新节点,让新节点的next指向header  
        //并以新节点作为新的header  
        Node newNode = new Node(element, null);  
        newNode.next = header;  
        header = newNode;  
           
        //若插入前是空表  
        if(tail == null){  
            tail = header;  
        }  
           
        size++;  
    }  
       
    //删除指定索引处的元素  
    public T delete(int index){  
           
        if(index < 0 || index > size-1){  
            throw new IndexOutOfBoundsException("索引超出线性表范围");  
        }  
           
        Node del = null;  
           
        //若要删除的是头节点  
        if(index == 0){  
            del = header;  
            header = header.next;  
        }  
        else{  
            Node prev = getNodeByIndex(index - 1);//获取待删除节点的前一个节点  
               
            del = prev.next;//获取待删除节点  
               
            prev.next = del.next;  
               
            del.next = null;//将被删除节点的next引用置为空  
        }  
           
        size--;  
        return del.data;  
    }  
       
    //删除最后一个元素  
    public T remove(){  
        return delete(size - 1);  
    }  
       
    //判断线性表是否为空  
    public boolean isEmpty(){  
        return size == 0;  
    }  
       
    //清空线性表  
    public void clear(){  
        //将header,tail置为null  
        header = null;  
        tail = null;  
        size = 0;  
    }  
       
    public String toString(){  
           
        if(isEmpty()){  
            return "[]";  
        }  
        else{  
            StringBuilder sb = new StringBuilder("[");  
            for(Node current = header; current != null; current = current.next){  
                sb.append(current.data.toString() + ", ");  
            }  
               
            int len = sb.length();  
               
            return sb.delete(len-2, len).append("]").toString();  
        }  
           
    }  
}  

四、测试代码

import org.junit.Test;  
   
import com.sihai.algorithm.LinkList;  
   
public class LinkListTest {  
   
    @Test  
    public void test() {  
   
        // 测试构造函数  
        LinkList<String> list = new LinkList("好");  
        System.out.println(list);  
   
        // 测试添加元素  
        list.add("放大");  
        list.add("没");  
        System.out.println(list);  
   
        // 在头部添加  
        list.addAtHead("啦啦啦");  
        System.out.println(list);  
   
        // 在指定位置添加  
        list.insert("膜拜", 2);  
        System.out.println(list);  
   
        // 获取指定位置处的元素  
        System.out.println("第2个元素是(从0开始计数):" + list.get(2));  
   
        // 返回元素索引  
        System.out.println("膜拜在的位置是:" + list.locate("膜拜"));  
        System.out.println("mobai所在的位置:" + list.locate("mobai"));  
   
        // 获取长度  
        System.out.println("当前线性表的长度:" + list.length());  
   
        // 判断是否为空  
        System.out.println(list.isEmpty());  
   
        // 删除最后一个元素  
        list.remove();  
        System.out.println("调用remove()后:" + list);  
   
        // 获取长度  
        System.out.println("当前线性表的长度:" + list.length());  
   
        // 删除指定位置处元素  
        list.delete(3);  
        System.out.println("删除第4个元素后:" + list);  
   
        // 获取长度  
        System.out.println("当前线性表的长度:" + list.length());  
   
        // 清空  
        list.clear();  
        System.out.println(list);  
   
        // 判断是否为空  
        System.out.println(list.isEmpty());  
    }  
   
}  

五、链表相关的常用操作实现方法

1. 链表反转
/**
     * 链表反转
     * 
     * @param head
     * @return
     */
    public Node ReverseIteratively(Node head) {
        Node pReversedHead = head;
        Node pNode = head;
        Node pPrev = null;
        while (pNode != null) {
            Node pNext = pNode.next;
            if (pNext == null) {
                pReversedHead = pNode;
            }
            pNode.next = pPrev;
            pPrev = pNode;
            pNode = pNext;
        }
        this.head = pReversedHead;
        return this.head;
    }
2. 查找单链表的中间节点

采用快慢指针的方式查找单链表的中间节点,快指针一次走两步,慢指针一次走一步,当快指针走完时,慢指针刚好到达中间节点。

/**
     * 查找单链表的中间节点
     * 
     * @param head
     * @return
     */
    public Node SearchMid(Node head) {
        Node p = this.head, q = this.head;
        while (p != null && p.next != null && p.next.next != null) {
            p = p.next.next;
            q = q.next;
        }
        System.out.println("Mid:" + q.data);
        return q;
    }
3. 查找倒数第k个元素

采用两个指针P1,P2,P1先前移K步,然后P1、P2同时移动,当p1移动到尾部时,P2所指位置的元素即倒数第k个元素 。

/**
     * 查找倒数 第k个元素
     * 
     * @param head
     * @param k
     * @return
     */
    public Node findElem(Node head, int k) {
        if (k < 1 || k > this.length()) {
            return null;
        }
        Node p1 = head;
        Node p2 = head;
        for (int i = 0; i < k; i++)// 前移k步
            p1 = p1.next;
        while (p1 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p2;
    }
4. 对链表进行排序
/**
     * 排序
     * 
     * @return
     */
    public Node orderList() {
        Node nextNode = null;
        int tmp = 0;
        Node curNode = head;
        while (curNode.next != null) {
            nextNode = curNode.next;
            while (nextNode != null) {
                if (curNode.data > nextNode.data) {
                    tmp = curNode.data;
                    curNode.data = nextNode.data;
                    nextNode.data = tmp;
                }
                nextNode = nextNode.next;
            }
            curNode = curNode.next;
        }
        return head;
    }
5. 删除链表中的重复节点
/**
     * 删除重复节点
     */
    public void deleteDuplecate(Node head) {
        Node p = head;
        while (p != null) {
            Node q = p;
            while (q.next != null) {
                if (p.data == q.next.data) {
                    q.next = q.next.next;
                } else
                    q = q.next;
            }
            p = p.next;
        }

    }
6. 从尾到头输出单链表,采用递归方式实现
/**
     * 从尾到头输出单链表,采用递归方式实现
     * 
     * @param pListHead
     */
    public void printListReversely(Node pListHead) {
        if (pListHead != null) {
            printListReversely(pListHead.next);
            System.out.println("printListReversely:" + pListHead.data);
        }
    }
7. 判断链表是否有环,有环情况下找出环的入口节点
/**
     * 判断链表是否有环,单向链表有环时,尾节点相同
     * 
     * @param head
     * @return
     */
    public boolean IsLoop(Node head) {
        Node fast = head, slow = head;
        if (fast == null) {
            return false;
        }
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                System.out.println("该链表有环");
                return true;
            }
        }
        return !(fast == null || fast.next == null);
    }

    /**
     * 找出链表环的入口
     * 
     * @param head
     * @return
     */
    public Node FindLoopPort(Node head) {
        Node fast = head, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast)
                break;
        }
        if (fast == null || fast.next == null)
            return null;
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
参考资料:

© 著作权归作者所有

共有 人打赏支持
公众号_好好学java
粉丝 61
博文 47
码字总数 144629
作品 0
赣州
程序员
私信 提问
自己动手写区块链(Java版)

2018年开始区块链真是火啊。一夜暴富的例子一直在传说。今天我们就自己动手写一个基本的区块链。 先简单的说一下区块链是个什么(相信你早就知道了)。 区块链就是一个链表。把一堆区块串起来...

全部原谅
08/07
0
0
数据结构(一) 单链表的实现-JAVA

数据结构还是很重要的,就算不是那种很牛逼的,但起码得知道基础的东西,这一系列就算是复习一下以前学过的数据结构和填补自己在这一块的知识的空缺。加油。珍惜校园中自由学习的时光。按照链...

时刻在奔跑
08/27
0
0
自己动手构建无锁的并发容器(栈和队列)

目录 1.前言 2. 基于CAS算法构建无锁的并发栈 2.1 数组实现 2.2 链表实现 2.3 性能测试 3. 基于CAS算法构建无锁的并发队列 3.1 入队方法 3.2 出队方法 3.3 性能测试 4. 总结 1.前言 并发容器...

takumiCX
08/11
0
0
C语言中关于释放单链表的问题

我现在用C在写一个图书管理系统,要求用链表来保存图书信息和链表信息。 现在我在写链表释放(我写的是单链表)的时候出错了。 代码如下 void freelist(bookinfo * bookinfohead ,userinfo ...

水晶之夜
2014/01/04
1K
11
面试题:将n个平均长度为m的有序队列组合成一个有序队列

写在前面的话:我写博客是为了训练自己的表达能力,更多是为了记录自己的一些工作思路,好记性不如烂笔头。所以博客写出来的内容不像写论文那样负责,写学术论文会反复修改几十遍,并且在投稿...

初雪之音
06/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

不可不说的Java“锁”事

前言 Java提供了种类丰富的锁,每种锁因其特性的不同,在适当的场景下能够展现出非常高的效率。本文旨在对锁相关源码(本文中的源码来自JDK 8)、使用场景进行举例,为读者介绍主流锁的知识点...

美团技术团队
1分钟前
0
0
ali oss util demo

package com.example.demo;import com.aliyun.oss.OSSClient;import com.aliyun.oss.common.utils.BinaryUtil;import com.aliyun.oss.model.*;import org.slf4j.Logger;import o......

经常把天聊死的胖子
3分钟前
0
0
Windows系统中eclipse修改字体为Courier New

背景:在eclipse修改字体时没有找到Courier New字体; 解决: 1.在计算机地址栏上输入“C:\Windows\Fonts”路径,回车打开Win10字体文件夹。查看是否有Courier New字体;如下图: 2.如果有该...

anlve
4分钟前
0
0
使用hexo做博客网站

hexo有什么用? hexo 可以把md文件生成html静态网页。 hexo官网:https://hexo.io/zh-cn/ 本地安装hexo。 npm install -g hexo-cli#生成blog(名字任意)文件夹,并且在这个文件夹里面初始化...

王坤charlie
4分钟前
0
0
RabbitMQ+PHP 教程四(Routing)用yii2测试通过

开始 在本教程中,我们将为它添加一个特性——我们将只可能订阅消息的一个子集。例如,我们只能够将关键错误消息直接指向日志文件(以节省磁盘空间),同时仍然能够打印控制台上的所有日志消...

hansonwong
8分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部