1.什么是链表
[1]. 链表是一种在物理存储单元上非连续的的存储结构;
[2]. 链表的数据单元分为:数据域(data:存储节点的数据信息)和指针域(next:存储下/上个节点的地址);
[3]. 链表可以分为:带头结点的链表和不带头结点的链表;
[4]. 基本链表分类:
(1)单链表
(2)循环链表
(3)双向链表
[5]. 带头结点的链表表示:
1.1 带头结点单链表的表示
2.单链表的基本操作
[1] 设置链表的结点结构:
数据域 和 指针域;
[2] 创建链表,并获取链表的长度 和 指定位置的结点元素;
[3] 插入结点:
① 找到需要插入的位置i的前一个结点;
② 在系统中生成一个空节点temp,将数据元素e赋值给temp->data;
③ 单链表标准插入语句:temp.next = p.next; p.next = temp;
④ 返回成功;
[4] 删除结点:
① 找到需要删除的位置i的前一个结点;
② 将p.next的结点中的数据赋值给num;
; ③ 单链表标准插入语句:p.next = p.next.next;
④ 返回成功;
[5] 删除链表中的倒数结点;(见代码)
[6] 链表倒序输出: (见代码)
3.单链表的代码实现
package com.LinkedList; /* * 带头单链表操作:(1-6 为基础;7-13为提高) * 1. 创建 * 2. 获取链表指定位置结点数据 * 3. 插入元素 * 4. 删除元素 * 5. 删除链表中的倒数第 i 个元素 * 6. 链表倒序输出 * 7. 链表反转 * 8. 判断链表是否有环 * 9. 判断链表是否为回文链表 * 10. 交换链表的相邻节点 * 11. 链表求和 * 12. 分隔链表 * 13. 将链表元素按照奇数偶数排列 * * */ public class DemoLinkedList { public static void main(String[] args) { // 1. 判断链表是否为空,若是,则创建链表 MyNode head = createLinkedList(); if(isEmpty(head)){ System.out.println("当前链表为空"); } System.out.println("链表长度:"+getLength(head)); System.out.print("遍历打印链表:"); printOut(head); // 2. 获取指定位置元素 data System.out.println("插入前,3号位置的元素数值:"+getNode(head,3)); // 3. 插入 insert(head,3,100); System.out.println("插入后,3号位置的元素数值:"+getNode(head,3)); System.out.print("遍历打印插入后的链表:"); printOut(head); // 4. 删除 delete(head,4); System.out.print("遍历打印删除后的链表:"); printOut(head); // 5. 删除链表的倒数第 index 个元素 deleteBackward(head,2); System.out.print("遍历打印删除倒数第2个节点后的链表:"); printOut(head); // 测试代码! /* deleteBackward(head,2); System.out.print("遍历打印删除倒数第2个节点后的链表:"); printOut(head); deleteBackward(head,1); System.out.print("遍历打印删除倒数第1个节点后的链表:"); printOut(head); deleteBackward(head,1); System.out.print("遍历打印删除倒数第1个节点后的链表:"); printOut(head);*/ // 6. 链表倒序输出 System.out.print("链表倒序输出为:"); printListReverse(head); System.out.print("\n"+"--------------------------"); } /* * 备注,注意: * MyNode curr = pHead; // curr指向pHead * MyNode node1 = new MyNode(pHead); // curr指向pHead的next * */ // 遍历打印输出,时间复杂度为O(n) // 对于递归方法,可参考倒序打印printListReverse(head); public static void printOut(MyNode pHead){ if(pHead == null){ System.out.println("链表为空!"); return; } MyNode curr = pHead; while(curr != null){ System.out.print(curr.data+" "); curr = curr.next; } System.out.println("\n"+"-------------------------------------"); return; } // 获取链表长度 public static int getLength(MyNode pHead){ MyNode temp = pHead; int length = 0; while(temp!=null){ length++; temp = temp.next; } return length; } // 1.1 创建链表 public static MyNode createLinkedList(){ MyNode node1 = new MyNode(1); MyNode node2 = new MyNode(2); MyNode node3 = new MyNode(3); MyNode node4 = new MyNode(4); node1.setNext(node2); node2.setNext(node3); node3.setNext(node4); return node1; } // 1.2 判断链表是否为空? public static boolean isEmpty(MyNode pHead){ if(pHead.next==null){ return true; } else{ return false; } } // 2. 获取指定位置index的元素数值 public static int getNode(MyNode pHead,int index){ MyNode p = pHead; for(int i=1; i < index ; i++){ p = p.next; if (p == null){ System.out.println("第"+index+"的元素不存在!"); return -1; } } return p.data; } // 3. 插入元素 // 首先判断index位置是否能插入数据, 能则插入;否则,此位置不存在; // 然后生成一个空节点元素 temp ,并将data赋值给它; // 最后执行插入操作; public static boolean insert(MyNode pHead,int index,int data){ if(index<0){ System.out.println("插入失败!"+index+"号位置不存在!"); } MyNode p = pHead; for(int i=1; i < index-1 ; i++){ p = p.next; if (p == null){ System.out.println("插入失败!"+"第"+index+"的元素不存在!"); return false; } } // 此时 p 指向带插入位置index 的前一个元素,执行插入; MyNode insertNode = new MyNode(data); insertNode.next = p.next; p.next = insertNode; System.out.println("插入成功!"); return true; } // 4. 删除链表指定元素 public static boolean delete(MyNode pHead,int index){ if(pHead.next == null|| index<0){ System.out.println("删除失败!"); } MyNode p = pHead; // 先找到 需要删除节点 的 前一个节点 for(int i=1; i < index-1 ; i++){ p = p.next; if (p == null||p.next == null){ System.out.println("删除失败!"+"第"+index+"的元素不存在!"); return false; } } // 创建一个新的节点,用来指向将被删除的节点元素 MyNode temp = new MyNode(); temp = p.next; // 执行删除 p.next = p.next.next; // 将要删除的节点数据保存在num中,并释放该节点 int num = temp.data; temp.next = null; return true; } // 5. 删除链表的倒数第 index 个元素 public static MyNode deleteBackward(MyNode pHead,int index){ if(index > getLength(pHead)||index<=0){ System.out.println("链表中无待删除元素!"); return pHead; } MyNode start = pHead; // 利用start作为标准,先将其移到链表正数的第index位置 // 然后start到链表最后的节点个数count, // 即为经过count个节点后,便找到需要删除的指定节点 // 但是需要注意:要找到待删除节点的前一个节点才能执行删除过程 while(index > 0){ index--; start = start.next; } if(start == null){ System.out.println("删除后,当前链表无元素!"); pHead.data = -1; return pHead; } MyNode p = pHead; while(start.next != null){ start = start.next; p = p.next; } int num = p.next.data; // 执行删除 p.next = p.next.next; return pHead; } // 6. 链表倒序输出 public static void printListReverse(MyNode pHead){ MyNode curr = pHead; if(curr != null && curr.next != null){ printListReverse(curr.next); } System.out.print(curr.data+" "); } }
4.运行结果
备注:学习过程中难免会出现很多错误,请大家指教!有问题可以直接评论我,谢谢!