当前位置:   article > 正文

数据结构之单链表_单链表的定义csdn

单链表的定义csdn

一、单链表的定义

单链表的数据是由一个个结点组成的,每个结点包含自身值和下一个节点的地址,只能从前向后遍历的结构。
链表就是由链表结点构成的大实体对象就叫链表

二、单链表的示意图

这里展示的是5个整形数据在链表中的存放方式

在这里插入图片描述

三、单链表的基本实现(无虚拟结点)

  1. 创建一个节点类
class Node{
    int data;//结点保存的数据
    Node next;//保存下一个结点的地址
    //三个构造方法
    public Node(){}
    public Node(int data){
        this.data = data;
    }
    public Node(int data, Node next){
        this.data = data;
        this.next = next;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  1. 创建一个链表类并初始化
public class SingleLinkedNote {
    //创建一个头结点,有了头才能往后遍历
    private Node head = null;
    //记录结点的个数
    private int size = 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  1. 链表的toString方法
public String toString(){
    String ret = "";
    for (Node node = head; node != null ; node = node.next) {
        ret += node.data;
        ret += "->";
    }
    ret += "NULL";
    return ret;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  1. 向当前的链表中添加一个新的结点,默认在链表的头部添加
public void addFir(int data){
    Node node = new Node(data);
    //,链表为空该结点就是第一个结点
    if (head == null) {
        head = node;
    } else {
    //链表不为空
        node.next = head;
        head = node;
    }
    size ++;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

在这里插入图片描述

  1. 按照索引位置插入结点
public void addByIndex(int index, int data) {
    Node node = new Node(data);
    if (index < 0 || index > size) {
        System.out.println("输入错误");
    }
    if (index == 0){
        addFir(data);
    } else {
        Node pre = head;
        //找前驱结点
        for (int i = 0; i < index - 1; i++) {
            pre = pre.next;
        }
        node.next = pre.next;
        pre.next = node;
        size ++;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

在这里插入图片描述

  1. 在链表的尾部插入新元素
public void addTail(int data) {
    addByIndex(size, data);
}
  • 1
  • 2
  • 3
  1. 判断索引的合法性
public boolean legal(int index) {
    //index == size索引越界了
    if (index < 0 || index >= size){
        System.out.println("不合法");
        return false;
    }
    return true;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  1. 查找第一个值为val的结点索引是多少
public int findIndex (int data) {
    int index = 0;
    for (Node x = head; x != null; x = x.next) {
        if (x.data == data) {
            return index;
        }
        index ++;
    }
    return -1;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  1. 查找链表中是否包含传入的值
public boolean contains(int data) {
    return findIndex(data) != -1;
}
  • 1
  • 2
  • 3
  1. 查询索引为index位置的结点值
public int findByIndex(int index) {
    if (legal(index)) {
        Node x = head;
        for (int i = 0; i < index; i++) {
            x = x.next;
        }
        return x.data;
    }
    return -1;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  1. 修改索引为index位置的结点值为newVal,返回修改前的节点值
public int setByIndex(int index, int newVal) {
    //判断合法性
    if (legal(index)) {
        int oldVal = findByIndex(index);
        Node x = head;
        //找索引位置的结点
        for (int i = 0; i < index; i++) {
            x = x.next;
        }
        //修改结点值
        x.data = newVal;
        return oldVal;
    }
    return -1;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  1. 删除单链表中索引为index位置的节点,返回删除前的节点值
public int removeByIndex(int index) {
    if (legal(index)) {
        //删除头结点
        if (index == 0) {
            Node x = head;
            head = head.next;
            x.next = null;
            size --;
            return x.data;
        }
        //删除其他结点,找前驱结点
        Node pre = head;
        for (int i = 0; i < index - 1; i++) {
            pre = pre.next;
        }
        int oldVal = pre.next.data;
        pre.next = pre.next.next;
        size --;
        return oldVal;
    }
    return -1;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  1. 删除链表中第一个值为val的元素
public void removeValOnce(int val) {
    int index = findIndex(val);
    removeByIndex(index);
}
  • 1
  • 2
  • 3
  • 4
  1. 删除链表中所有值为val的结点
public void removeAllVal(int val) {
    //头节点不为空,循环判断头节点是否为要删除的
    while (head!= null && head.data == val ) {
        head = head.next;
        size --;
    }
    //链表里没元素了
    if (head == null) {
        return;
    } else {
        //找前驱
        for (Node pre = head; pre != null; pre = pre.next) {
            //循环判断是否是要删除的结点
            while(pre.next != null && pre.next.data == val) {
                pre.next = pre.next.next;
                size --;
            }
        }
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  1. 删除头节点
public void removeFir(){
    removeByIndex(0);
}
  • 1
  • 2
  • 3
  1. 删除尾节点
public void removeTail(){
    removeByIndex(size - 1);
}
  • 1
  • 2
  • 3

四、单链表的实现(带虚拟头结点)

示意图

在这里插入图片描述

  1. 链表类的定义
public class SingleLinkHead {
    //虚拟节点,不存放任何值
    private Node dummyHead = new Node();
    private int size;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  1. 头插
public void addFir(int data) {
	//由下图可知,插入的结点的next就是虚拟节点的下一个结点
    Node node = new Node(data,dummyHead.next);
    dummyHead.next = node;
    size ++;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

在这里插入图片描述

  1. 在索引为index的位置插入新元素val
public void addByIndex(int index, int data) {
        if(index < 0 || index > size){
            System.out.println("输入错误");
        }
        //找前驱结点
        Node pre = dummyHead;
    	//因为虚拟结点为索引0,所以找前驱的时候要+1,所以<index
        for (int i = 0; i < index; i++) {
            pre = pre.next;
        }
        pre.next = new Node(data,pre.next);
        size ++;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  1. 删除单链表中索引为index位置的节点,返回删除前的节点值
public int removeByIndex(int index){
    if(legal(index)){
        //找前驱结点
        Node pre = dummyHead;
        for (int i = 0; i < index; i++) {
            pre = pre.next;
        }
        Node node = pre.next;
        int oldVal = node.data;
        pre.next = node.next;
        node.next = null;
        size --;
        return oldVal;
    }
    return -1;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  1. 删除链表所有值为val的元素
public void removeAllVal(int val) {
    for (Node pre = dummyHead; pre != null; pre = pre.next) {
        while (pre.next != null && pre.next.data == val) {
            pre.next = pre.next.next;
            size --;
        }
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  1. 判断合法性
private boolean legal(int index) {
    if (index < 0 || index >= size) {
        return false;
    }
    return true;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  1. 链表的toString方法
public String toString(){
    String ret = "";
    for (Node x = dummyHead; x.next != null; x= x.next) {
        ret += x.next.data;
        ret += "->";
    }
    ret += "NULL";
    return ret;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

五、总结

数据结构与算法比较复杂,需要多画图。链表题多判断边界。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/2023面试高手/article/detail/429818
推荐阅读
相关标签
  

闽ICP备14008679号