单链表实例解析参考

  一、概述

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

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

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

  二、图解

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

  新增节点:

  将值为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 {

  // 定义一个内部类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

  if(i == index){

  return current;

  }

  }

  return null;

  }

  //按值查找所在位置

  public int locate(T element){

  Node current = header;

for(int i=0; i

  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 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;

  }


链表资料便于学习参考

单链表

http://www.makeru.com.cn/live/5413_1924.html?s=45051

循环链表及线性表的应用

http://www.makeru.com.cn/course/details/1902?s=45051

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 211,376评论 6 491
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,126评论 2 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 156,966评论 0 347
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,432评论 1 283
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,519评论 6 385
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,792评论 1 290
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,933评论 3 406
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,701评论 0 266
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,143评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,488评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,626评论 1 340
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,292评论 4 329
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,896评论 3 313
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,742评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,977评论 1 265
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,324评论 2 360
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,494评论 2 348

推荐阅读更多精彩内容