Java实现单链表，实现链表的插入和删除

发表于 分类于 评论数：
本文字数： 1.9k 阅读时长 ≈ 2 分钟

创建自定义的类和构造方法来实现简单的单链表。将结点结构定义为私有内部类，在外部类中对链表结构进行初始化，包括头结点和初始大小。

单链表操作原理不难，难点在于对链表进行插入和删除操作时，对于指针交换和分配的逻辑。

插入：找到要插入的位置 i 后，用新结点的后继指针替换 i 的后继指针，再将 i 的后继指针指向该新结点。

删除：将要删除位置的后继指针指向下下个元素。

整表创建：注意头插法和尾插法的逻辑，详见代码注释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
package SqList;
/**
 * 单链表
 * @author YJC
 *
 */
public class SingleLinkedList {
	//定义链表
	private int size;//链表节点的个数
	private Node head;//头节点

	public SingleLinkedList() {
		size = 0;
		head = null;
	}

	//链表的结点类
	private class Node{
		private Object data;//每个节点的数据
		private Node next;//结点指向下一个节点的指针

		public Node(Object data) {
			this.data = data;
		}
	}

	//查找链表中第i个元素,返回给e
	public Node find(int i,Object e) {
		Node current = head;
		int temp = 1;
		while(temp<i) {
			current = current.next;
			temp++;
		}
		e = current;
		return (Node) e;
	}


	//在第i个位置前插入新的元素e
	public Object insert(int i,Object e) {
		Node newNode = new Node(e);//新建一个节点
		Node current = head;
		int temp = 1;
		while(temp<i) {
			current = current.next;
			temp++;
		}
		newNode.next = current.next;
		current.next = newNode;
		return newNode;
	}

	//删除第i个结点
	public void delete(int i) {
		int temp = 1;
		Node current = head;
		while(temp<i && current!=null) {
			current = current.next;
			temp++;
		}
		current.next = current.next.next;

	}


	//单链表的整表创建,头插法  加入n个元素到单链表
	public void createAtHead(int n) {
		Node head = null;//头结点指向null，即建立一个带头结点的单链表
		for(int i=0;i<n;i++) {
			Node node = new Node(Math.random()*100+1);//生成1-100的数字
			node.next = head;
			head = node;
		}
	}

	public void createAtTail(int n) {
		for (int i = 0; i < n; i++) {
			Node node = new Node(Math.random() * 100 + 1);// 生成1-100的数字

			Node tempNode = head;
			while (null != tempNode.next) {
				tempNode = tempNode.next;//寻找尾结点
			}
			//此时tempNode是尾结点
			node.next = tempNode.next;//null，把node定义为尾结点，后继指针为null
			tempNode.next = node;//当前尾结点的后继指针指向node
		}
	}
}
0%