链表的原理及java实现代码示例

一:单向链表基本介绍

链表是一种数据结构,和数组同级。比如,Java中我们使用的ArrayList,其实现原理是数组。而LinkedList的实现原理就是链表了。链表在进行循环遍历时效率不高,但是插入和删除时优势明显。下面对单向链表做一个介绍。

单链表的概念

链表是最基本的数据结构,其存储的你原理图如下图所示

上面展示的是一个单链表的存储原理图,简单易懂,head为头节点,他不存放任何的数据,只是充当一个指向链表中真正存放数据的第一个节点的作用,而每个节点中都有一个next引用,指向下一个节点,就这样一节一节往下面记录,直到最后一个节点,其中的next指向null。

链表有很多种,比如单链表,双链表等等。我们就对单链表进行学习,其他的懂了原理其实是一样的。

单向链表是一种线性表,实际上是由节点(Node)组成的,一个链表拥有不定数量的节点。其数据在内存中存储是不连续的,它存储的数据分散在内存中,每个结点只能也只有它能知道下一个结点的存储位置。由N各节点(Node)组成单向链表,每一个Node记录本Node的数据及下一个Node。向外暴露的只有一个头节点(Head),我们对链表的所有操作,都是直接或者间接地通过其头节点来进行的。

上图中最左边的节点即为头结点(Head),但是添加节点的顺序是从右向左的,添加的新节点会被作为新节点。最先添加的节点对下一节点的引用可以为空。引用是引用下一个节点而非下一个节点的对象。因为有着不断的引用,所以头节点就可以操作所有节点了。

下图描述了单向链表存储情况。存储是分散的,每一个节点只要记录下一节点,就把所有数据串了起来,形成了一个单向链表。

节点(Node)是由一个需要储存的对象及对下一个节点的引用组成的。也就是说,节点拥有两个成员:储存的对象、对下一个节点的引用。下面图是具体的说明:

二、单项链表的实现

package com.zjn.LinkAndQueue;
/**
 * 自定义链表设计
 *
 * @author zjn
 *
 */
public class MyLink {
	Node head = null;
	// 头节点
	/**
   * 链表中的节点,data代表节点的值,next是指向下一个节点的引用
   *
   * @author zjn
   *
   */
	class Node {
		Node next = null;
		// 节点的引用,指向下一个节点
		int data;
		// 节点的对象,即内容
		public Node(int data) {
			this.data = data;
		}
	}
	/**
   * 向链表中插入数据
   *
   * @param d
   */
	public void addNode(int d) {
		Node newNode = new Node(d);
		// 实例化一个节点
		if (head == null) {
			head = newNode;
			return;
		}
		Node tmp = head;
		while (tmp.next != null) {
			tmp = tmp.next;
		}
		tmp.next = newNode;
	}
	/**
   *
   * @param index:删除第index个节点
   * @return
   */
	public Boolean deleteNode(int index) {
		if (index < 1 || index > length()) {
			return false;
		}
		if (index == 1) {
			head = head.next;
			return true;
		}
		int i = 1;
		Node preNode = head;
		Node curNode = preNode.next;
		while (curNode != null) {
			if (i == index) {
				preNode.next = curNode.next;
				return true;
			}
			preNode = curNode;
			curNode = curNode.next;
			i++;
		}
		return false;
	}
	/**
   *
   * @return 返回节点长度
   */
	public int length() {
		int length = 0;
		Node tmp = head;
		while (tmp != null) {
			length++;
			tmp = tmp.next;
		}
		return length;
	}
	/**
   * 在不知道头指针的情况下删除指定节点
   *
   * @param n
   * @return
   */
	public Boolean deleteNode11(Node n) {
		if (n == null || n.next == null)
		      return false;
		int tmp = n.data;
		n.data = n.next.data;
		n.next.data = tmp;
		n.next = n.next.next;
		System.out.println("删除成功!");
		return true;
	}
	public void printList() {
		Node tmp = head;
		while (tmp != null) {
			System.out.println(tmp.data);
			tmp = tmp.next;
		}
	}
	public static void main(String[] args) {
		MyLink list = new MyLink();
		list.addNode(5);
		list.addNode(3);
		list.addNode(1);
		list.addNode(2);
		list.addNode(55);
		list.addNode(36);
		System.out.println("linkLength:" + list.length());
		System.out.println("head.data:" + list.head.data);
		list.printList();
		list.deleteNode(4);
		System.out.println("After deleteNode(4):");
		list.printList();
	}
}

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

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实现代码示例的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站:

Java编程实现递增排序链表的合并

Java面试题-实现复杂链表的复制代码分享

Java输出链表倒数第k个节点

如有不足之处,欢迎留言指出。

(0)

相关推荐

  • Java数据结构之简单链表的定义与实现方法示例

    本文实例讲述了Java数据结构之简单链表的定义与实现方法.分享给大家供大家参考,具体如下: 一.概述: 1.原理: 只有一个数据项(链接点Link),每个数据插入时都是对第一个数据的引用. 2.插入数据说明: 当链表没有数据时,插入的值就是第一个数据,如果链表里有数据,就把当前的数据的next指针指向第一个数据. 3.插入数据图: 4.特点:先进后出 5.实现功能: 数据插入,指定位置插入,显示,查询,删除等 6.删除原理 7.插入头节点原理 二.实现: 1.创建节点 /** * @描述 节点

  • Java实现单向链表的基本功能详解

    一.前言 最近在回顾数据结构与算法,有部分的算法题用到了栈的思想,说起栈又不得不说链表了.数组和链表都是线性存储结构的基础,栈和队列都是线性存储结构的应用- 本文主要讲解单链表的基础知识点,做一个简单的入门-如果有错的地方请指正 二.回顾与知新 说起链表,我们先提一下数组吧,跟数组比较一下就很理解链表这种存储结构了. 2.1回顾数组 数组我们无论是C.Java都会学过: 数组是一种连续存储线性结构,元素类型相同,大小相等 数组的优点: 存取速度快 数组的缺点: 事先必须知道数组的长度 插入删除元

  • Java实现单向链表反转

    本文实例为大家分享了Java实现单向链表反转的具体代码,供大家参考,具体内容如下 1.实现代码 public class LinkedListTest { public static void main(String[] args) { Node A = new Node("A"); Node B = new Node("B"); Node C = new Node("C"); Node D = new Node("D");

  • java使用链表来模拟栈的入栈出栈操作实例代码

    栈:后进先出:最后一个放入堆栈中的物体总是被最先拿出来. 使用链表来模拟栈的入栈出栈操作. 1.节点类代码 public class Entry<T> { private T value; private Entry<T> next; public Entry() { this(null); } public Entry(T value) { this.value=value; this.next=null; } public void setValue(T value) { th

  • Java数据结构之链表、栈、队列、树的实现方法示例

    本文实例讲述了Java数据结构之链表.栈.队列.树的实现方法.分享给大家供大家参考,具体如下: 最近无意中翻到一本书,闲来无事写几行代码,实现几种常用的数据结构,以备后查. 一.线性表(链表) 1.节点定义 /**链表节点定义 * @author colonel * */ class Node { public int data; Node next=null; public Node(int data){ this.data=data; } } 2.链表操作类 /**链表操作类 * @auth

  • 链表的原理及java实现代码示例

    一:单向链表基本介绍 链表是一种数据结构,和数组同级.比如,Java中我们使用的ArrayList,其实现原理是数组.而LinkedList的实现原理就是链表了.链表在进行循环遍历时效率不高,但是插入和删除时优势明显.下面对单向链表做一个介绍. 单链表的概念 链表是最基本的数据结构,其存储的你原理图如下图所示 上面展示的是一个单链表的存储原理图,简单易懂,head为头节点,他不存放任何的数据,只是充当一个指向链表中真正存放数据的第一个节点的作用,而每个节点中都有一个next引用,指向下一个节点,

  • SQL注入原理与解决方法代码示例

    一.什么是sql注入? 1.什么是sql注入呢? 所谓SQL注入,就是通过把SQL命令插入到Web表单递交或输入域名或页面请求的查询字符串,最终达到欺骗服务器执行恶意的SQL命令,比如先前的很多影视网站泄露VIP会员密码大多就是通过WEB表单递交查询字符暴出的,这类表单特别容易受到SQL注入式攻击.当应用程序使用输入内容来构造动态sql语句以访问数据库时,会发生sql注入攻击.如果代码使用存储过程,而这些存储过程作为包含未筛选的用户输入的字符串来传递,也会发生sql注入. 黑客通过SQL注入攻击

  • 多模字符串匹配算法原理及Java实现代码

    多模字符串匹配算法在这里指的是在一个字符串中寻找多个模式字符字串的问题.一般来说,给出一个长字符串和很多短模式字符串,如何最快最省的求出哪些模式字符串出现在长字符串中是我们所要思考的.该算法广泛应用于关键字过滤.入侵检测.病毒检测.分词等等问题中.多模问题一般有Trie树,AC算法,WM算法等等. 背景 在做实际工作中,最简单也最常用的一种自然语言处理方法就是关键词匹配,例如我们要对n条文本进行过滤,那本身是一个过滤词表的,通常进行过滤的代码如下 for (String document : d

  • 深度优先与广度优先Java实现代码示例

    在编程生活中,我们总会遇见树性结构,这几天刚好需要对树形结构操作,就记录下自己的操作方式以及过程.现在假设有一颗这样树,(是不是二叉树都没关系,原理都是一样的) 1.深度优先 英文缩写为DFS即Depth First Search. 深度优先搜索是一种在开发爬虫早期使用较多的方法.它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) .在一个HTML文件中,当一个超链被选择后,被链接的HTML文件将执行深度优先搜索,即在搜索其余的超链结果之前必须先完整地搜索单独的一条链.深度

  • 冒泡排序算法原理及JAVA实现代码

    冒泡排序法:关键字较小的记录好比气泡逐趟上浮,关键字较大的记录好比石块下沉,每趟有一块最大的石块沉底. 算法本质:(最大值是关键点,肯定放到最后了,如此循环)每次都从第一位向后滚动比较,使最大值沉底,最小值上升一次,最后一位向前推进(即最后一位刚确定的最大值不再参加比较,比较次数减1) 复杂度: 时间复杂度 O(n2) ,空间复杂度O(1) JAVA源代码(成功运行,需要Date类) 复制代码 代码如下: public static void bubbleSort(Date[] days) { 

  • Java编程实现邻接矩阵表示稠密图代码示例

    我们知道,要表示结点,我们可以用一个一维数组来表示,然而对于结点和结点之间的关系,则无法简单地用一维数组来表示了,我们可以用二维数组来表示,也就是一个矩阵形式的表示方法. 我们假设A是这个二维数组,那么A中的一个元素aij不仅体现出了结点vi和结点vj的关系,而且aij的值正可以表示权值的大小. 邻接矩阵模型类 邻接矩阵模型类的类名为AMWGraph.java,能够通过该类构造一个邻接矩阵表示的图,且提供插入结点,插入边,取得某一结点的第一个邻接结点和下一个邻接结点. import java.u

  • java&javascript自定义加密数据传输代码示例

    在开发应用过程中,客户端与服务端经常需要进行数据传输,涉及到重要隐私信息时,开发者自然会想到对其进行加密,即使传输过程中被"有心人"截取,也不会将信息泄露.对于加密算法,相信不少开发者也有所耳闻,比如MD5加密,Base64加密,DES加密,AES加密,RSA加密等等..可利用亦或,并,且,等进行简单加密. 示例代码中使用的^运算key=0x01,可自定义自己的规则.定义自己的运算,保证可逆数据不丢失即可.key也可定义,动态key. java代码 public static Stri

  • SQL提取数据库表名及字段名等信息代码示例

    本文向大家介绍了使用SQL语句提取数据库所有表的表名.字段名的实例代码,在SQLserver 中进行了测试,具体内容如下: --查询所有用户表所有字段的特征 SELECT D.Name as TableName, A.colorder AS ColOrder, A.name AS Name, COLUMNPROPERTY(A.ID,A.Name, 'IsIdentity') AS IsIdentity, CASE WHEN EXISTS (SELECT 1 FROM dbo.sysobjects

  • Java语言实现反转链表代码示例

    问题描述 定义一个函数,输入一个链表的头结点,反转该链表并输出反转后的链表的头结点.链表结点如下: public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } 思路1: 要想反转链表,对于结点i,我们要把它的next指向它的前趋,因此我们需要保存前趋结点,同时,如果我们已经把i的next重新赋值,会无法找到i的后继,因此,在重新赋值之前,我们要保存i的后继. 代码:

  • Java编程Iterator迭代器设计原理及实现代码示例

    我们知道迭代器(Iterator)是一种对象,它能够用来遍历标准模板库容器中的部分或全部元素.那么Iterator迭代器的设计原理是什么呢?迭代器问什么定义了一个借口,而不是一个类呢? 我们假设迭代器迭代数据的功能定义为了一个类,那么,会有这样的问题.不同的集合,由于数据结构不一样,所以他们的存储方式也是不一样的.也就是说,迭代器获取的时候,获取的方式是变化的,也就是不固定的.所以把这种方式定义为具体的实现是不合理的. 无论何种集合,他们肯定都有获取的功能,而且不知道什么时候就没有数据了.所有他

随机推荐