单链表链表是有序的列表
截图.png
- 链表是以节点的方式来存储，是链式存储的
- 每个节点包含data域，next域：指向下一个节点
- 如图：链表的各个节点不一定连续存储
- 链表分带头节点的链表和没有带头节点的链表，根绝实际的需求来确定
创建，新增，修改，删除链表代码实现：
package com.swh.data;
import com.alibaba.fastjson.JSON;
public class LinkedList {
public static void main(String[] args) {
Node node1 = new Node(23, "向喀什23");
Node node2 = new Node(40, "向喀什40");
Node node3 = new Node(20, "向喀什20");
Node node4 = new Node(39, "向喀什39");
SingleLinked singleLinked = new SingleLinked();
singleLinked.addNode(node1);
singleLinked.addNode(node2);
singleLinked.addNode(node3);
singleLinked.addNode(node4);
singleLinked.addNode(node4);
singleLinked.updateNode(40, "my name is 40");
singleLinked.delete(23);
singleLinked.showNode();
singleLinked.delete(40);
singleLinked.delete(39);
singleLinked.delete(20);
singleLinked.delete(20);
singleLinked.showNode();
}
}
class SingleLinked {
private Node head = new Node(0, "");
// 添加链表
public void addNode(Node node) {
// 获取最后一个节点
Node temp = head;
while (true) {
if (temp.getNo() == node.getNo()) {
System.out.println("添加的节点已经存在了！！ no->" + node.getNo() + " name->" + node.getName());
return;
}
if (temp.getNext() == null) {
temp.setNext(node);
return;
}
if (temp.getNext().getNo() > node.getNo()) {
node.setNext(temp.getNext());
temp.setNext(node);
return;
}
temp = temp.getNext();
}
}
// 修改链表
public void updateNode(int no, String name) {
Node temp = head.getNext();
while (true) {
if (temp == null) {
System.out.println("链表中无数据~");
return;
}
if (temp.getNo() == no) {
temp.setName(name);
return;
}
if (temp.getNo() != no && temp.getNext() == null) {
System.out.printf("未查询到编号为%d的数据信息\n", no);
return;
}
temp = temp.getNext();
}
}
//删除列表
public void delete(int no) {
Node temp = head;
while (true) {
if (temp.getNext() == null) {
System.out.printf("未查询到编号为%d的数据信息", no);
return;
}
if (temp.getNext().getNo() == no) {
temp.setNext(temp.getNext().getNext());
return;
}
temp = temp.getNext();
}
}
public void showNode() {
Node temp = head.getNext();
while (true) {
if (temp == null) {
System.out.println("链表中无数据~");
return;
}
System.out.println(temp.toString());
if (temp.getNext() == null)
return;
temp = temp.getNext();
}
}
}
class Node {
private int no;
private String name;
private Node next;
public Node(int no, String name) {
this.no = no;
this.name = name;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
@Override
public String toString() {
return "Node{" +
"no=" + no +
", name='" + name + '\'' +
'}';
}
}
单链表的常见面试题有如下:
1)求单链表中有效节点的个数
思路:直接遍历链表中的数据
//求链表中的个数 直接遍历链表
public int getSize() {
Node temp = head.getNext();
int size = 0;
while (true) {
if (temp == null) {
System.out.println("链表中无数据~");
return size;
}
size++;
temp = temp.getNext();
}
}
2）查找单链表中的倒数第k个节点【新浪】
// 查找单链表中的倒数第K个节点
// 思路:获取总条数 然后求出正数多少个 然后进行遍历求出、
public Node getFromBehindKNode(int k) {
// 获取总条数
int size = getSize();
k = size - k + 1;
if (k <= 0) {
System.out.println("请在链表的范围内查询");
return null;
}
Node temp = head.getNext();
int count = 0;
while (true) {
if (temp == null) {
System.out.println("链表中无数据~");
return null;
}
count++;
if (count == k) return temp;
temp = temp.getNext();
}
}
3）单链表的反转【腾讯】
//单链表的反转
//思路 : 遍历链表 把遍历到的节点迁移到第一个
public void reverse(){
if(head.getNext()==null){ // 如果发现链表为空就直接返回
System.out.println("链表为空");
return;
}
Node temp = head.getNext();
while (true){
Node next= null;
// 当第一个节点是最后一个节点时就不需要进行移动了
if((next=temp.getNext())==null)return;
// 1.把当前节点的指针指向下下一个节点
temp.setNext(next.getNext());
// 2.将获取到的节点设置成第一个节点
next.setNext(head.getNext());
head.setNext(next);
}
}
4）从尾到头打印单链表【百度，要求方式1 :反向遍历 方式2 stack栈】
public void reversePrint() {
Node temp = head.getNext();
if (temp == null) {
System.out.println("链表为空");
return;
}
Stack<Node> stack = new Stack();
while (true) {
if (temp == null) break;
stack.push(temp);
temp = temp.getNext();
}
while (stack.size()>0){
System.out.println("链表中的信息->"+JSON.toJSONString(stack.pop().getNext().getNo()));
}
}
5）合并两个有序的单链表，合并之后的链表依然有序
