欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构 链表实现插入、删除(Java)

程序员文章站 2022-03-01 23:19:57
...
package 链表;

import java.util.Scanner;

public class 链表 {

	public static void main(String[] args) {
		ListNode head = new ListNode(0);
		head.add(1);
		head.add(2);
		head.add(3);
		System.out.println("初始链表为:");
		head.print();
		System.out.println();
		head.ListInsert(head);
		System.out.println();
		head.ListDelete(head);
	}
}

class ListNode {
	int data;//数据域
	ListNode next;//next指针域
	ListNode (int x) {
		data = x;
	}
	public ListNode() {
	}
	
	//添加新的结点
	public void add(int newData) {
		ListNode newNode = new ListNode(newData);
		if(this.next == null) {
			this.next = newNode;
		}else {
			this.next.add(newData);;
		}
	}
	
	//打印链表
	public void print() {
		System.out.print(this.data);
		if(this.next != null) {
			System.out.print("-->");
			this.next.print();
		}
	}
	

//插入
public void ListInsert(ListNode node) {
	System.out.println("请输入要插入结点的位置和值:");
	Scanner sc = new Scanner(System.in);
	int i = sc.nextInt();//位置
	int e = sc.nextInt();//要插入的元素
	ListNode p = node;
	int j = 0;
	if(p == null) {
		//System.out.println("插入位置非法");
		return;
	}
	while(p != null && j < i - 1) {
		p = p.next;
		++j;//寻找到i-1个节点,找到前一个插入位置
	}
	if(p == null || j > i - 1) return;//i小于1 或者大于表长+1
	ListNode q = new ListNode();//生成新节点
	//具体的插入操作
	q.data = e;
	q.next = p.next;
	p.next = q;
	System.out.println("插入元素后:");
	node.print();
}

//删除结点
public void ListDelete(ListNode head) {
	System.out.println("请输入要删除的结点位置:");//删除第i个节点
	Scanner sc = new Scanner(System.in);
	int i = sc.nextInt();
	ListNode p = head;
	ListNode q = null;
	int j = 0;
	while(p.next != null && j < i - 1) {//找到要删除的位置
		p = p.next;
		++j;
	}
	if(p.next == null || j > i - 1) {
		//System.out.println("删除位置不合理");
		return;
	}
	//开始删除结点
	q = p.next;
	p.next = q.next;//删除并释放结点
	//这块释放第i个节点的空间
	System.out.println("删除结点后");
	head.print();
}
}