博客

Java数据结构-双向链表增、删、改等操作

稍后还会有环形链表及约瑟夫问题等，链表就告一段落。

再往后就是栈等结构

package Doublelinked;

import java.util.Stack;


public class doublelinked {

	public static void main(String[] args) {
		
		// 1.创建节点进行测试
		Node node1 = new Node(1, "宋江", "及时雨");
		Node node2 = new Node(2, "卢俊义", "玉麒麟");
		Node node3 = new Node(3, "吴用", "智多星");
		Node node4 = new Node(4, "林冲", "豹子头");
		Node node5 = new Node(5, "武松", "脑斧终结者");
		//2.创建链表
		SingleLinkedListNode singlelinkedlistnode = new SingleLinkedListNode();
	
//		//3.将创建的节点加入链表,按先后顺序添加
//		 singlelinkedlistnode.add(node1);
//		 singlelinkedlistnode.add(node4);
//		 singlelinkedlistnode.add(node2);
//		 singlelinkedlistnode.add(node3);
//		 singlelinkedlistnode.add(node5);
		
		//3.将创建的节点加入链表,按节点序号先后顺序添加
		singlelinkedlistnode.addbyorder(node1);
		singlelinkedlistnode.addbyorder(node4);
		singlelinkedlistnode.addbyorder(node2);
		singlelinkedlistnode.addbyorder(node3);
		singlelinkedlistnode.addbyorder(node5);
		// 显示链表
		singlelinkedlistnode.list();
		//4.修改节点
		Node newnode = new Node(4, "MC.大冲", "MC.我豹哥");
		//5.将新节点替换插入到链表中
		singlelinkedlistnode.update(newnode);
		System.out.printf("修改后的情况\n");
		singlelinkedlistnode.list();
	
		//6.删除一个节点
		singlelinkedlistnode.del(2);
		System.out.printf("删除后的情况\n");
		singlelinkedlistnode.list();
	}
}

/*******************************************************************************/
	/*
	 * 模块一： 创建链表节点类
	 */
class Node {
	public int no; // 位次
	public String name; // 名字
	public String nickname; // 绰号
	public Node next; // 指向下一节点
	public Node pre;	//指向前一节点
	
	
	// 构造器,封装节点内信息，构造一次即一个节点模块
	public Node(int Nno, String Nname, String Nnickname) {
		this.no = Nno;
		this.name = Nname;
		this.nickname = Nnickname;
	}
	// 显示方法，重新toString
	@Override
	public String toString() {
		return "Node [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
		}
	}
	
/**************************************************************************************/	
/*
 * 模块二： 建立链表并定义各种操作
 */
class SingleLinkedListNode {
		
		//初始化头结点，不存放任何数据
	public Node head = new Node(0,"","");
	
	//定义方法，导出私有变量
	public Node getHead() {
		return head;
	}
	/*思路一:
	 * 不考虑编号时，添加节点到链表尾部
	 * 1.找到当前链表尾部位置
	 * 2.将最后一个节点的next指针指向新节点
	 * */
	/*功能1：
	 * 添加数据进链表
	 * */
	public void add(Node node) {	//开始创建添加新节点
		//头节点不能动，添加一个新的节点指针
		Node temp = head;
		//遍历链表，找到链表最后.设置死循环，当符合循环内条件时跳出
		while(true) {
			if(temp.next==null) {	//只有头节点时
				break;
			}
			//当前节点不是尾节点时不断后移
			temp.next.pre = temp;
			temp = temp.next;
			
		}
		//运行到当前语句代表已经找到尾节点
		temp.next = node;
	//添加完毕
	}	
	
	
/*思路二：
 * 考虑节点信息，按编号顺序插入链表
 * 功能1：
 * */	
	public void addbyorder(Node node) {
		Node temp = head;
		boolean flag = false;   //设置标签，当符合条件时变为true，根据flag判断是否可插入新节点
		while(true) {
			if(temp.next==null) {//在链表最后
				break;
			}
			if(temp.next.no>node.no) {//找到了合适位置，temp后插入即可
				break;
			}else if(temp.next.no==node.no) {//编号已经存在
				flag=true;
				break;
			}
			temp = temp.next;
		}
		//判断flag值
		if(flag) {
			System.out.printf("编号%d已经存在，不能加入\n",node.no);
			
		}else if(temp.next ==null){
			//位置插入（两种情况，①尾部插入②中间插入）
			//①如果尾部插入
			temp.next = node;
			node.pre = temp;
//			node.next = temp.next;
//			temp.next = node;
		}else {
			//②中间插入
			node.next = temp.next;
			temp.next = node;
			temp.next.pre = node;
			node.pre = temp;
		}
	}
	
		

	/*功能2：
	 * 显示链表数据
	 * */
	public void list() {
		//判断链表是否为空
		if(head.next==null) {
			System.out.println("链表为空~~~~");
			return;
		}
		
		Node temp = head;//重新定义指示头节点
		while(true) {//定义死循环
			if(temp==null) {//若temp.next==null则直接把最后一条数据清除了
				break;
			}
			//输出节点信息
			System.out.println(temp);
			temp = temp.next;//节点后移，输出下一节点做准备
		}
	}
	
	/*功能3:
	 * 修改节点信息，no编号不可修改
	 * */
	
	public void update(Node newnode) {
		if(head.next ==null) {	//若链表为空
			System.out.printf("链表为空。无法修改节点\n");
			return;
		}
		//找到需要修改的节点
		Node temp = head.next;//定义辅助变量在头节点后面
		
		boolean flag = false;	//用来表示是否找到了该节点
		while(true) {		//定义死循环，找到节点时跳出
			if(temp==null) {
				break;//已经遍历完毕
			}
			if(temp.no ==newnode.no) {	//找到新节点
				flag = true;
				break;
			}
			temp = temp.next;
		}
		//根据flag判断是否找到了修改节点
		if(flag) {
			temp.name = newnode.name;
			temp.nickname = newnode.nickname;
		}else {
			System.out.printf("没有找到编号为%d的节点", newnode.no);
		}
		
	}
	
	/*功能3：
	 * 删除节点
	 * 头节点不能动，需要temp指示待删除节点
	 *比较的时候是temp.no与待删除节点no比较
	 * */
	
	public void del(int no) {
		if(head.next ==null) {	//若链表为空
			System.out.printf("链表为空。无法删除修改节点\n");
			return;
		}
		//找到需要删除修改的节点
		Node temp = head;//定义辅助变量在头节点后面
		
		boolean flag = false;	//用来表示是否找到了该节点
		while(true) {		//定义死循环，找到节点时跳出
			if(temp.next==null) {
				break;//已经遍历完毕
			}
			if(temp.no ==no) {	//找到待删除节点
				flag = true;
				break;
			}
			temp = temp.next;
		}
		//根据flag判断是否找到了删除修改节点
		if(flag) {
			if(temp.next != null) {
				temp.pre.next = temp.next;
				temp.next.pre = temp.pre;
			}else if(temp.next == null){
				temp.pre.next = null;
				}
			}
			else {
			System.out.printf("没有找到编号为%d的节点", no);
			}		
	}
	
}