文档章节

自己动手写一个单链表

公众号_好好学java
 公众号_好好学java
发布于 06/20 07:24
字数 1984
阅读 545
收藏 8
点赞 2
评论 0

文章有不当之处,欢迎指正,如果喜欢微信阅读,你也可以关注我的微信公众号:好好学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
粉丝 52
博文 41
码字总数 120629
作品 0
赣州
程序员
C语言中关于释放单链表的问题

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

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

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

初雪之音
06/28
0
0
rt-thread中用消息队列实现广播功能的一种方法

前面几天在逛论坛时看见有人说RTT中没有广播机制,于是心血来潮,想自己动手写一个,于是有了此文. 1 广播机制分析 广播,这个词首先让我想到Android下的广播机制,其是基于Binder来实现的,然而R...

长平狐
2013/03/19
572
0
请写一个程序,找到两个单链表最开始的交叉节点。

我的回答内存溢出,怎么优化。。。。 请写一个程序,找到两个单链表最开始的交叉节点。 注意事项 如果两个链表没有交叉,返回null。 在返回结果后,两个链表仍须保持原有的结构。 可假定整个...

从余
2017/01/14
368
4
数据结构(C语言版)第四章:链表

4.1 指针 实际上并不推荐使用malloc和free,使用malloc还简单,但是当指针进行移动的时候,你如何确定在哪个地址上free内存,则是个大难题. 我们写个正常的malloc和free程序: #include <stdio.h...

fzyz_sb
2013/12/06
0
0
数据结构之链表c语言实现

准备把原来上学时候写的数据结构、算法相关的代码再重新写一遍,温习下。首先从链表说起,链表可能是我们平时用的较多的一种结构,链表操作对于删除、添加的算法时间复杂度为O(1)。 说到链表...

菏泽小朱
2016/10/17
0
0
面试 7:快慢指针法玩转链表算法面试(一)

面试 7:面试常见的链表类算法捷径 链表是我们数据结构面试中比较容易出错的问题,所以很多面试官总喜欢在这上面下功夫,为了避免出错,我们最好先进行全面的分析。在实际软件开发周期中,设...

nanchen2251
07/12
0
0
链表的C语言实现(含动态内存分配)

链表的C语言实现(含动态内存分配) 上 链表的C语言实现之动态内存分配 一、为什么用动态内存分配 但我们未学习链表的时候,如果要存储数量比较多的同类型或同结构的数据的时候,总是使用一个数...

晨曦之光
2012/03/09
612
0
走出浮躁的泥沼:关于技术与工作

关于技术与工作 我觉得,技术与工作最理想的结合状态是,自己能学习到新的技术,这些技术也能应用到工作中;工作的内容又不那么枯燥,都那么具有挑战性。 程序员的工作首先应该是富有挑战性的...

蟋蟀哥哥
2012/11/30
6.8K
89
深入分析 Linux 内核链表

一、 链表数据结构简介 链表是一种常用的组织有序数据的数据结构,它通过指针将一系列数据节点连接成一条数据链,是线性表的一种重要实现方式。相对于数组,链 表具有更好的动态性,建立链表...

nothingfinal
2012/02/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

ConcurrentLinkedQueue源码分析

前言 ConcurrentLinkedQueue是一个线程安全的队列,它采用的是 CAS 算法来进行实现,也就是说它是非阻塞的;队列中的元素按照 FIFO(先进先出)的原则对元素进行排列,此外,它是一个无界队列;...

tsmyk0715
8分钟前
0
0
String,StringBuffer ,StringBuilder的区别

不同点 一、基类不同 StringBuffer、StringBuilder 都继承自AbStractStringBuilder,String 直接继承自 Object 2、底层容器“不同” 虽然底层都是字符数组,但是String的是final修饰的不可变...

不开心的时候不要学习
19分钟前
0
0
nodejs 文件操作

写文件code // 加载文件模块var fs = require("fs");var content = 'Hello World, 你好世界!';//params 文件名,内容,编码,回调fs.writeFile('./hello.txt',content,'utf8',function (er......

yanhl
22分钟前
0
0
SpringBoot mybits 查询为0条数据 但是在Navicat 中可以查询到数据

1.页面请求: 数据库查询: 2018-07-16 17:56:25.054 DEBUG 17312 --- [nio-9010-exec-3] c.s.h.m.C.selectSelective : ==> Preparing: select id, card_number, customer_id, customer_nam......

kuchawyz
31分钟前
0
0
译:Self-Modifying cod 和cacheflush

date: 2014-11-26 09:53 翻译自: http://community.arm.com/groups/processors/blog/2010/02/17/caches-and-self-modifying-code Cache处在CPU核心与内存存储器之间,它给我们的感觉是,它具......

我叫半桶水
34分钟前
0
0
Artificial Intelligence Yourself

TensorFlow是谷歌基于DistBelief进行研发的第二代人工智能学习系统,其命名来源于本身的运行原理。Tensor(张量)意味着N维数组,Flow(流)意味着基于数据流图的计算,TensorFlow为张量从流...

孟飞阳
46分钟前
0
0
press.one个人数字签名

这是我在press.one的数字签名 https://press.one/p/address/v?s=9d3d5b7ce019af357ab994775549e8f047a5b17fc9893364652fc67e4b95443b38ccb24c6655e0d252dd0154369eb9b7717c4ccf4e1835ca3596......

NateHuang
49分钟前
1
0
Oracle 中的 SQL 分页查询原理和方法详解

本文分析并介绍 Oracle 中的分页查找的方法。 Oracle 中的表,除了我们建表时设计的各个字段,其实还有两个字段(此处只介绍2个),分别是 ROWID(行标示符)和 ROWNUM(行号),即使我们使用...

举个_栗子
55分钟前
2
2
C++ iostream、iomanip 头文件详解

大家好,我是ChungZH!这是我的第二篇博客。在这篇博客中,我将介绍一些有关C++的iostream和iomanip库的知识,希望大家喜欢! 首先,我们来看看iostream。 相信大家都知道iostream,这个库可以...

ChungZH
今天
1
0
atom的摸索

atom中使用git 软件有提示,不赘述(软件的特色) 提供的只是些基础功能,我们需要伟大的开源伙伴来解决易用性问题 ,安装git plus插件,你就可以不用cli也可以在atom中畅快的使用git了 因为这玩意...

狮子狗
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部