头插法创建链表

发表于 分类于 ， ， Waline： 本文字数： 4.3k 阅读时长 ≈ 4 分钟

头插法创建链表

思想：把新创建的节点插入到头节点的前面作为新的头节点。

代码

成员变量

1
2
private int data;
private Node next;

头插法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 使用头插入法创建链表。
 * 所谓头插法，就是新创建的节点插入到旧的头结点的前面，作为新的头结点。
 * 
 * @return 链表的头结点的引用(地址)
 */
public static Node createLinkByHead() {
	Node h = null;
    Node n = null;
	Scanner scanner = new Scanner(System.in);
	int input = -1;
	while ((input = scanner.nextInt()) > 0) {
		// 创建一个节点
		n = new Node(input);
		// 头节点的地址赋值给新节点
		// 新节点连接到头结点上
		n.next = h;
		// 以新节点作为新的头结点
		h = n;
	}
	return h;
}

代码执行过程示意图

方法开始执行时，先创建Node的引用变量h和n,此时h和n并没有引用对象。他们的值都为null,如下图所示：

1
2
3
4
5
6
7
8
9
10
11
/*
1:   Node head=null
*/
digraph demo {
    rankdir=LR;
    node [shape=record];
    h [shape=ellipse];
    n [shape=ellipse];
    n -> null [color="red"];
    h -> null [color="red"];
}

用户从键盘输入一个大于0的数字之后，这里假设输入的是1，
则会创建一个Node对象，并把该对象的地址赋值给引用变量n.
如下图所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
2:  n=new Node(1);
*/
digraph demo {
    rankdir=LR;
    node [shape=record];
    h [shape=ellipse];
    n [shape=ellipse];

    a [label="{1|}"];
    
    h -> null;
    n ->a [color="red"];
}

此时创建的节点是第1个节点，它后面没有旧的节点，所以该节点的地址域应该赋值为null,因为head的值也是null,所以这里设置为head的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
2:  Node n=new Node(1);
3:  n.next=null,也就是n.next=head
*/
digraph demo {
    rankdir=LR;
    node [shape=record];
    h [shape=ellipse];
    n [shape=ellipse];

    a [label="{1|null}" color="red"];
    
    h -> null;
    n ->a;
}

接下来把这个新创建的直接的地址赋值给头指针h:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
2:  n=new Node(1);
3:  n.next=null,也就是n.next=head
新创建的节点的地址赋值给头指针h
4:  h=n;
*/
digraph demo {
    rankdir=LR
    node [shape=record]
    null
    h [shape=ellipse]
    n [shape=ellipse]
    a [label="{1|null}"]
    // h -> null
    
    n -> a
    h -> a [color="red"]
}

然后，再次创建一个新的节点，地址赋值给引用变量n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
再次创建一个节点，并把地址赋值给指针n
5: n=new Node(2);
*/
digraph demo {
    rankdir=LR
    node [shape=record]
    h [shape=ellipse]
    n [shape=ellipse]
    n1 [label="{1|null}"]
    n2 [label="{2|}"]
    // null [shape=ellipse]
    
    // h -> null
    n -> n2 [color="red"]
    h -> n1
}

新创建的节点的地址域记录下链表的头节点的地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
把头指针h中保存的地址赋值给新创建的节点的地址域
6:  n.next=head;
*/
digraph demo {
    rankdir=LR
    node [shape=record]
    h [shape=ellipse]
    n [shape=ellipse]
    n1 [label="{1|null}"]
    n2 [label="{2|}"]

    n -> n2
    n2 -> n1 [color="red"]
    h -> n1
}

头指针记录新创建的节点的地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
把头指针h中保存的地址赋值给新创建的节点的地址域
6:  n.next=head
头指针保存新创建的节点的地址
7: h=n;
*/
digraph demo {
    rankdir=LR
    node [shape=record]
    h [shape=ellipse]
    n [shape=ellipse]

    n1 [label="{1|null}"]
    n2 [label="{2|}"]

    n -> n2
    n2 -> n1
    h -> n2 [color="red"]
}

然后在次创建一个新节点，地址记录在指针n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
再次创建一个节点，并把地址赋值给指针n
8:  n=new Node(2);
*/
digraph demo {
    rankdir=LR
    node [shape=record]
    h [shape=ellipse]
    n [shape=ellipse]
    n1 [label="{1|null}"]
    n2 [label="{2|}"]
    n3 [label="{3|}"] [color="red"]

    n -> n3 [color="red"]
    h -> n2
    n2 -> n1
}

新创建的节点的地址域记录头节点的地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
再次创建一个节点，并把地址赋值给指针n
8:  n=new Node(2);
把头指针h保存的地址赋值给新创建的节点的地址域
9:  n.next=h;
*/
digraph demo {
    rankdir=LR
    node [shape=record]
    h [shape=ellipse]
    n [shape=ellipse]
    n1 [label="{1|null}"]
    n2 [label="{2|}"]
    n3 [label="{3|}"]

    n -> n3
    n3 -> n2 [color="red"]
    n2 -> n1
    h -> n2
}

头指针记录下新创建的节点的地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
头指针保存新创建的节点的地址
10: h=n;
*/
digraph demo {
    rankdir=LR
    node [shape=record]
    h [shape=ellipse]
    n [shape=ellipse]
    n1 [label="{1|null}"]
    n2 [label="{2|}"]
    n3 [label="{3|}"]

    n -> n3
    n3 -> n2
    n2 -> n1

    h -> n3 [color="red"]
}

再次创建一个新的节点，地址记录在指针n中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
再次创建一个节点，并把地址赋值给指针n
11:  n=new Node(3);
*/
digraph demo {
    rankdir=LR
    node [shape=record]
    h [shape=ellipse]
    n [shape=ellipse]
    n1 [label="{1|null}"]
    n2 [label="{2|}"]
    n3 [label="{3|}"]
    n4 [label="{4|}"] [color="red"]

    n -> n4 [color="red"]

    h -> n3
    n3 -> n2
    n2 -> n1
}

新创建的节点记录头节点的地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
新创建的节点的地址域记录头结点的地址
12: n.next=h;
*/
digraph demo {
    rankdir=LR
    node [shape=record]
    h [shape=ellipse]
    n [shape=ellipse]
    n1 [label="{1|null}"]
    n2 [label="{2|}"]
    n3 [label="{3|}"]
    n4 [label="{4|}"]

    n -> n4
    n4 -> n3 [color="red"]
    n3 -> n2
    n2 -> n1

    h -> n3
}