自己动手写一个单链表

文章有不当之处,欢迎指正,如果喜欢微信阅读,你也可以关注我的微信公众号:好好学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;
    }
参考资料:

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏乐沙弥的世界

MongoDB 单键(列)索引

764
来自专栏张狗蛋的技术之路

MySQL探秘(三):InnoDB的内存结构和特性

 常言说得好,每个成功男人背后都有一个为他默默付出的女人,而对于MySQL来说,这个“人”就是InnoDB存储引擎。  MySQL区别于其他数据库的最为重要的特...

1072
来自专栏Python小屋

Python编程常见出错信息及原因分析(2)

(1)缩进错误 演示代码: >>> if 5>3: print('5>3') SyntaxError: expected an indented block >...

3497
来自专栏Jack的Android之旅

疯狂java笔记之栈和队列栈队列双端队列

栈的英文单词是Stack,它代表一种特殊的线性表,这种线性表只能在固定一端(通常认为是线性表的尾端)进行插入,删除操作。

743
来自专栏好好学java的技术栈

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

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

Oozie分布式工作流——流控制

最近又开始捅咕上oozie了,所以回头还是翻译一下oozie的文档。文档里面最重要就属这一章了——工作流定义。 一提到工作流,首先想到的应该是工作流都支持...

18710
来自专栏老九学堂

【超全】C语言小白最容易犯的17种错误,你中了几个?

C编译的程序对语法检查并不像其它高级语言那么严格,这就给编程大佬们留下了“灵活的余地”,但还是由于这个灵活给程序的调试带来了许多不便,尤其对刚刚接触C语言的人来...

3305
来自专栏青枫的专栏

Linux的头文件和C/C++的头文件

=============================================================================

672
来自专栏大数据架构

Spark CommitCoordinator 保证数据一致性

本文通过 Local mode 执行如下 Spark 程序详解 commit 原理

763
来自专栏友弟技术工作室

Go 程序的基本结构和要素

示例 package main import "fmt" func main() { fmt.Println("hello, world") } 包...

30911

扫码关注云+社区