链表的简单介绍

• 什么是链表
  链表是一种物理存储单元上非连续、非顺序的存储结构。数据元素的逻辑顺序是通过链表的指针链接实现的
• 链表当中的每一个元素称为一个结点，这些结点可以在程序运行的过程中动态的生成
• 每一个结点分为两个区域：
  data域（存放数据元素）
  next域（存放的是下一个结点的地址）
• 链表的特点：
  插入或删除中间的元素是效率高，查找效率低。
• 链表的分类：
  单向链表、双向链表、环形链表

单向链表

单向链表结构图

代码实现

模拟结点

//模拟结点
public class Node {
    //存放在data域中的数据
    public int id;
    public String name;
    public double price;
    //next域：指向下一个结点
    public Node next;

    public Node(int id, String name, double price) {
        this.id = id;
        this.name = name;
        this.price = price;
    }
    @Override
    public String toString() {
         return "Node{id=" + id + ", name='" + name + "', price=" + price + '}';
    }
}

遍历所有结点

//模拟单向链表
public class SingleLinklist {
    //头节点
    private Node headNode= new Node(0,"",0.0);
     /** * 遍历单项链表 */
    public void show(){
    	//如果头节点的next为空则说明当前链表为空
        if (headNode.next == null) {
            System.out.println("当前链表为空");
            return;
        }
        Node temp = headNode;
        while (true){
        	//当前结点没有下一个结点
            if (temp.next == null){
                break;
            }
            temp = temp.next;
            System.out.println(temp);
        }
    }
}

按顺序添加结点

这个方法写在SingleLinklist 类中

/** * 添加结点(追加在链表的尾端) */
	public void add(Node goodsNode){
        Node temp = headNode;
        while(true){
            if (temp.next == null) {
                //如果这个结点的next域为空就跳出while循环
                break;
            }
            //将下一个结点赋值给temp
            temp = temp.next;
        }
        temp.next=goodsNode;
    }

测试

public class LinkTest {
    public static void main(String[] args) {
        Node node1 = new Node(1,"nike",699);
        Node node2 = new Node(2,"adidas",499);
        Node node3 = new Node(3,"vans",399);
        Node node4 = new Node(4,"lining",599);
        SingleLinklist link = new SingleLinklist();

        //测试按顺序插入
        link.add(node1);
        link.add(node2);
        link.add(node3);
        link.add(node4);
        //遍历结点
        link.show();
   }
}

根据id添加结点

/** * 根据id进行添加（插入） */
    public void addById(Node goodsNode){
        //用来判断id是否重复
        boolean flg = false;
        Node temp = headNode;
        while(true){
            if (temp.next == null){
                //当前结点没有下一个结点
                break;
            }
            if (temp.next.id > goodsNode.id){
                //当下一个结点的id值大于要插入结点的id值时跳出循环
                break;
            }else if(temp.next.id == goodsNode.id){
                //id重复 默认id重复就不添加结点
                flg = true;
                break;
            }
            temp = temp.next;
        }
        if (flg){
            //如果id重复就不插入结点
            System.out.println("id重复，无法插入");
        }else {
        	//插入结点
            goodsNode.next = temp.next;
            temp.next = goodsNode;
        }
    }

测试

public class LinkTest {
    public static void main(String[] args) {
        Node node1 = new Node(1,"nike",699);
        Node node2 = new Node(2,"adidas",499);
        Node node3 = new Node(3,"vans",399);
        Node node4 = new Node(4,"lining",599);
        SingleLinklist link = new SingleLinklist();
        //测试按id值插入
        link.addById(node4);
        link.addById(node3);
        link.addById(node2);
        link.addById(node1);
        link.show();
	}
}

根据id修改结点

/** * 修改结点 * 1.先找到链表中的目标结点 * 2.根据新的数据修改结点 */
    public void update(Node goodsNode){
        if (headNode.next == null){
            System.out.println("链表为空");
            return;
        }
        Node temp = headNode;
        //判断是否找到目标结点
        boolean isFind = false;
        while (true){
            if (temp.next == null){
                //遍历完整个链表还没找到目标结点
                break;
            }
            if (temp.id == goodsNode.id){
                //找到目标结点
                isFind = true;
                break;
            }
            temp = temp.next;
        }
        if (isFind){
            //修改结点
            temp.name = goodsNode.name;
            temp.price = goodsNode.price;
        }else{
            System.out.println("没有找到目标找到目标结点");
        }
    }

测试

public class LinkTest {
    public static void main(String[] args) {
        Node node1 = new Node(1,"nike",699);
        Node node2 = new Node(2,"adidas",499);
        Node node3 = new Node(3,"vans",399);
        Node node4 = new Node(4,"lining",599);
        SingleLinklist link = new SingleLinklist();

        //测试按顺序插入
        link.add(node1);
        link.add(node2);
        link.add(node3);
        link.add(node4);
        //测试修改
        Node node5 = new Node(2,"anta",299);
        link.update(node5);
        link.show();
	}
}

根据id删除结点

/** * 根据id删除结点 */
public void delete(Node goodsNode){
    if (headNode.next == null){
        System.out.println("链表为空");
        return;
    }
    Node temp = headNode;
    boolean isFind = false;
    while (true){
        if (temp.next == null){
            //遍历到整个链表还没找到目标结点
            //System.out.println("没有找到目标找到目标结点");
            break;
        }
        if (temp.next.id == goodsNode.id){
            //找到目标结点
            isFind = true;
            break;
        }
        temp = temp.next;
    }
    if (isFind){
        //删除结点
        temp.next = temp.next.next;
    }else{
        System.out.println("没有找到目标找到目标结点");
    }
}

测试

public class LinkTest {
    public static void main(String[] args) {
        Node node1 = new Node(1,"nike",699);
        Node node2 = new Node(2,"adidas",499);
        Node node3 = new Node(3,"vans",399);
        Node node4 = new Node(4,"lining",599);
        SingleLinklist link = new SingleLinklist();

        //测试按顺序插入
        link.add(node1);
        link.add(node2);
        link.add(node3);
        link.add(node4);
        //测试删除
        link.delete(node3);
        link.show();
	}
}