介绍
链表是有序的列表(List)，物理存储结构如下所示
逻辑结构如下
链表的特点主要有
- 以节点方式存储，链式存储
- 每个节点包含data、next指针，next指向下一个节点
- 各个节点的物理地址不一定连续
代码实现
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
|
package com.eh.ftd.dsa.ds.impl;
/**
* todo
*
* @author David Li
* @create 2020/06/16 14:24
*/
public class SingleLinkedList<E> {
private Node head = new Node();
/**
* 首先定义一个节点用来包装数据
*
* @param <E>
*/
class Node<E> {
private E e;
private Node next;
public Node() {
}
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
@Override
public String toString() {
return "Node{" +
"e=" + e +
'}';
}
}
/**
* 增加一个元素
*
* @param e
* @return
*/
public boolean add(E e) {
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = new Node(e, null);
return true;
}
/**
* 用来演示
*/
public void display() {
Node temp = head;
while (temp.next != null) {
temp = temp.next;
System.out.println(temp.e);
}
}
public static void main(String[] args) {
SingleLinkedList list = new SingleLinkedList();
list.add(1);
list.add(2);
list.add(3);
list.display();
}
}
|
几道单链表相关的面试题
求链表的倒数第k个元素
- 先遍历获取链表元素个数n
- 遍历获取第(n-k)个元素
在原有的链表基础上逆序
传送门： 单向链表逆序
合并两个有序列表
比较简单，直接给出代码
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
|
public static SingleLinkedList mergeDemo(SingleLinkedList list1, SingleLinkedList list2) {
SingleLinkedList list = new SingleLinkedList();
Node cur1 = list1.head.next;
Node cur2 = list2.head.next;
while (cur1 != null || cur2 != null) {
if (cur1 == null) {
list.add(cur2);
cur2 = cur2.next;
continue;
}
if (cur2 == null) {
list.add(cur1);
cur1 = cur1.next;
continue;
}
int val1 = (int) cur1.e;
int val2 = (int) cur2.e;
if (val1 < val2) {
list.add(cur1);
cur1 = cur1.next;
} else if (val1 == val2) {
list.add(cur1);
list.add(cur2);
cur1 = cur1.next;
cur2 = cur2.next;
} else {
list.add(cur2);
cur2 = cur2.next;
}
}
return list;
}
public static void main(String[] args) {
SingleLinkedList list1 = new SingleLinkedList();
list1.add(1);
list1.add(3);
list1.add(5);
list1.add(7);
SingleLinkedList list2 = new SingleLinkedList();
list2.add(2);
list2.add(4);
list2.add(6);
list2.add(8);
list2.add(9);
list2.add(10);
list2.add(11);
System.out.println("========合并后的结果========");
SingleLinkedList list = mergeDemo(list1, list2);
list.display();
}
|
运行结果
