单向链表的介绍和实现思路(单向链表是什么)

  本篇文章为你整理了单向链表的介绍和实现思路(单向链表是什么)的详细内容,包含有单向链表结构图 单向链表是什么 单向链表的定义 单向链表的优点和缺点 单向链表的介绍和实现思路,希望能帮助你了解 单向链表的介绍和实现思路。

  链表在内存中的存储

  特点

  链表是以节点的方式来存储,是链式存储

  每个节点包含 data 域 和 next 域。next域用来指向下一个节点

  链表的各个节点不一定是连续存储的

  链表分带头节点的链表和没有头节点的链表,根据实际的需求来确定

  带头结点的逻辑示意图

  创建(添加)

  先创建一个Head头节点,表示单链表的头

  后面我们每添加一个节点,就放在链表的最后

  遍历

  通过一个辅助变量,来遍历整个链表

  有序插入

  先遍历链表,找到应该插入的位置

  要插入的节点的next指向插入位置的后一个节点

  插入位置的前一个节点的next指向要插入节点

  插入前要判断是否在队尾插入

  
翻转链表

  创建一个新的头结点,作为新链表的头

  从头遍历旧链表,将遍历到的节点插入新链表的头结点之后

  注意需要用到两个暂存节点

  一个用来保存正在遍历的节点

  一个用来保存正在遍历节点的下一个节点

  
 

  逆序打印

  遍历链表,将遍历到的节点入栈

  遍历完后,进行出栈操作,同时打印出栈元素

  代码

  

public class Demo1 {

 

   public static void main(String[] args) {

   LinkedList linkedList = new LinkedList();

   linkedList.traverseNode();

   System.out.println();

   //创建学生节点,并插入链表

   StudentNode student1 = new StudentNode(1, "Nyima");

   StudentNode student3 = new StudentNode(3, "Lulu");

   linkedList.addNode(student1);

   linkedList.addNode(student3);

   linkedList.traverseNode();

   System.out.println();

   //按id大小插入

   System.out.println("有序插入");

   StudentNode student2 = new StudentNode(0, "Wenwen");

   linkedList.addByOrder(student2);

   linkedList.traverseNode();

   System.out.println();

   //按id修改学生信息

   System.out.println("修改学生信息");

   student2 = new StudentNode(1, "Hulu");

   linkedList.changeNode(student2);

   linkedList.traverseNode();

   System.out.println();

   //根据id删除学生信息

   System.out.println("删除学生信息");

   student2 = new StudentNode(1, "Hulu");

   linkedList.deleteNode(student2);

   linkedList.traverseNode();

   System.out.println();

   //获得倒数第几个节点

   System.out.println("获得倒数节点");

   System.out.println(linkedList.getStuByRec(2));

   System.out.println();

   //翻转链表

   System.out.println("翻转链表");

   LinkedList newLinkedList = linkedList.reverseList();

   newLinkedList.traverseNode();

   System.out.println();

   //倒叙遍历链表

   System.out.println("倒序遍历链表");

   newLinkedList.reverseTraverse();

   * 创建链表

  class LinkedList {

   //头节点,防止被修改,设置为私有的

   private StudentNode head = new StudentNode(0, "");

   * 添加节点

   * @param node 要添加的节点

   public void addNode(StudentNode node) {

   //因为头节点不能被修改,所以创建一个辅助节点

   StudentNode temp = head;

   //找到最后一个节点

   while (true) {

   //temp是尾节点就停止循环

   if(temp.next == null) {

   break;

   //不是尾结点就向后移动

   temp = temp.next;

   //现在temp是尾节点了,再次插入

   temp.next = node;

   * 遍历链表

   public void traverseNode() {

   System.out.println("开始遍历链表");

   if(head.next == null) {

   System.out.println("链表为空");

   //创建辅助节点

   StudentNode temp = head.next;

   while(true) {

   //遍历完成就停止循环

   if(temp == null) {

   break;

   System.out.println(temp);

   temp = temp.next;

   * 按id顺序插入节点

   * @param node

   public void addByOrder(StudentNode node) {

   //如果没有首节点,就直接插入

   if(head.next == null) {

   head.next = node;

   return;

   //辅助节点,用于找到插入位置和插入操作

   StudentNode temp = head;

   //节点的下一个节点存在,且它的id小于要插入节点的id,就继续下移

   while (temp.next!=null temp.next.id node.id) {

   temp = temp.next;

   //如果temp的下一个节点存在,则执行该操作

   //且插入操作,顺序不能换

   if(temp.next != null) {

   node.next = temp.next;

   temp.next = node;

   * 根据id来修改节点信息

   * @param node 修改信息的节点

   public void changeNode(StudentNode node) {

   if(head == null) {

   System.out.println("链表为空,请先加入该学生信息");

   return;

   StudentNode temp = head;

   //遍历链表,找到要修改的节点

   while (temp.next!= null temp.id != node.id) {

   temp = temp.next;

   //如果temp已经是最后一个节点,判断id是否相等

   if(temp.id != node.id) {

   System.out.println("未找到该学生的信息,请先创建该学生的信息");

   return;

   //修改学生信息

   temp.name = node.name;

   * 根据id删除节点

   * @param node 要删除的节点

   public void deleteNode(StudentNode node) {

   if(head.next == null) {

   System.out.println("链表为空");

   return;

   StudentNode temp = head.next;

   //遍历链表,找到要删除的节点

   if(temp.next!=null temp.next.id!=node.id) {

   temp = temp.next;

   //判断最后一个节点的是否要删除的节点

   if(temp.next.id != node.id) {

   System.out.println("请先插入该学生信息");

   return;

   //删除该节点

   temp.next = temp.next.next;

   * 得到倒数的节点

   * @param index 倒数第几个数

   * @return

   public StudentNode getStuByRec(int index) {

   if(head.next == null) {

   System.out.println("链表为空!");

   StudentNode temp = head.next;

   //用户记录链表长度,因为head.next不为空,此时已经有一个节点了

   //所以length初始化为1

   int length = 1;

   while(temp.next != null) {

   temp = temp.next;

   length++;

   if(length index) {

   throw new RuntimeException("链表越界");

   temp = head.next;

   for(int i = 0; i length-index; i++) {

   temp = temp.next;

   return temp;

   * 翻转链表

   * @return 反转后的链表

   public LinkedList reverseList() {

   //链表为空或者只有一个节点,无需翻转

   if(head.next == null head.next.next == null) {

   System.out.println("无需翻转");

   LinkedList newLinkedList = new LinkedList();

   //给新链表创建新的头结点

   newLinkedList.head = new StudentNode(0, "");

   //用于保存正在遍历的节点

   StudentNode temp = head.next;

   //用于保存正在遍历节点的下一个节点

   StudentNode nextNode = temp.next;

   while(true) {

   //插入新链表

   temp.next = newLinkedList.head.next;

   newLinkedList.head.next = temp;

   //移动到下一个节点

   temp = nextNode;

   nextNode = nextNode.next;

   if(temp.next == null) {

   //插入最后一个节点

   temp.next = newLinkedList.head.next;

   newLinkedList.head.next = temp;

   head.next = null;

   return newLinkedList;

   public void reverseTraverse() {

   if(head == null) {

   System.out.println("链表为空");

   StudentNode temp = head.next;

   //创建栈,用于存放遍历到的节点

   Stack StudentNode stack = new Stack ();

   while(temp != null) {

   stack.push(temp);

   temp = temp.next;

   while (!stack.isEmpty()) {

   System.out.println(stack.pop());

   * 定义节点

  class StudentNode {

   int id;

   String name;

   //用于保存下一个节点的地址

   StudentNode next;

   public StudentNode(int id, String name) {

   this.id = id;

   this.name = name;

   @Override

   public String toString() {

   return "StudentNode{" +

   "id=" + id +

   ", name=" + name + \ +

   };

  

 

  
本文来自,作者:腹白,转载请注明原文链接:https:///wyh518/

  以上就是单向链表的介绍和实现思路(单向链表是什么)的详细内容,想要了解更多 单向链表的介绍和实现思路的内容,请持续关注盛行IT软件开发工作室。

郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。

留言与评论(共有 条评论)
   
验证码: