“365算法每日学计划”:04打卡-自己动手写一个单链表

一、概述

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

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

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

二、图解

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

这里写图片描述

新增节点:

将值为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;
    }
参考资料:
  • https://www.cnblogs.com/ganchuanpu/p/7468555.html
  • https://blog.csdn.net/jianyuerensheng/article/details/51200274

原文发布于微信公众号 - 好好学java(SIHAIloveJAVA)

原文发表时间:2018-06-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏狮乐园

dart class overview

最近在折腾 flutter 相关的东西,所以当然要撸一下 dart 了。编程语言这个东西,接触得多了学习起来速度会提升不少,但是不同的语言具有不同的特色,我们需...

942
来自专栏ShaoYL

OC语言Block 续

32312
来自专栏Google Dart

Dart语言指南(一) 顶

此文着重展示如何使用Dart语言的每一个主要功能,从变量和操作符到类和库,假设您已经知道如何用另一种编程语言。

802
来自专栏Java技术分享

XMLDTD语法详解

本文详细介绍DTD,包括其对元素的定义,属性的定义,以及实体的定义。

1909
来自专栏Jack-Cui

Day3、Python

题目 输入一行字符,分别统计出其中英文字母、空格、数字和其它字符的个数。 1、程序分析     根据题意可知,需要用到字符串的操作方法。本题中要用到的三...

1740
来自专栏逻辑熊猫带你玩Python

Python | 6大数据类型方法归纳总结(中)

可以直接使用tuple()创建一个新的元组,或者,使用tuple()将一个对象转换成元组。

964
来自专栏ShaoYL

OC语言Block 续

1219
来自专栏xingoo, 一个梦想做发明家的程序员

MFC常用基本数据类型

ATOM                   原子(原子表中的一个字符串的参考)  BOOL   布尔变量  BOOLEAN                布尔...

1656
来自专栏老司机的简书

老司机出品——源码解析之从Block说开去

近来把《iOS与OS X多线程和内存管理》这本书又掏出来看了一遍,这本书前前后后加起来看了能有三四遍了,每次看都有新的理解。现在就把个人对Block的一些理解记...

773
来自专栏進无尽的文章

编码篇-iOS程序中的内存分配 栈区堆区全局区等相关知识

在计算机的系统中,运行的应用程序中的数据都是保存在内存中,不同类型的数据,保存的内存区域不同。内存区域大致可以分为:栈区、堆区、全局区(静态区)、文字常量区、程...

842

扫码关注云+社区