Java数据结构：链表

单链表（Linked List）

链表是有序的列表，但是它在内存中的存储方式如下

image

1）链表是以节点的方式来存储,是链式存储

2）每个节点包含 data 域：存放数据， next 域：指向下一个节点的地址.

3）如图：发现链表的各个节点不一定是连续存储.

4）链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定;头节点不存放具体的数据，只用来表示单链表表头next域；

下面是单链表的逻辑结构：

双向链表

• 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。
• 单向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以自我删除。
• 比单向列表多了一个pre域：用于存放上一个节点的地址。

使用代码实现单链表：

public class Java {     
  public static void main(String[] args) {               
    HeroNode a1 = new HeroNode(1,"老色皮1","哈哈1");
    HeroNode a2 = new HeroNode(2,"老色皮2","哈哈2");
    HeroNode a3 = new HeroNode(4,"老色皮3","哈哈3");
    HeroNode a4 = new HeroNode(3,"老色皮2","哈哈2");

       HeroLinklist list = new HeroLinklist();
       list.add(a1);
       list.add(a2);
       list.addByNo(a4);
       list.add(a3);
   
       HeroNode a = new HeroNode(1,"老色皮5","哈哈5");
       list.update(a);
       list.delete(2);
       list.list();
    }
}
//定义链表方法
class HeroLinklist{
//先初始化一个头节点，不存放具体数据
private HeroNode head = new HeroNode(0,"","");

//添加方法，直接添加到链表尾部
public void add(HeroNode heroNode) {
    HeroNode temp = head;
    //遍历节点，找到最后一个节点
    while(true) {
        if(temp.next == null) {
            break;
        }
        //不是的话就继续下一个
        temp = temp.next;
    }
    //将最后的节点指向新的节点
    temp.next = heroNode;
}

//列出链表数据
public void list() {
    HeroNode temp = head;
    //判断链表是否为空
    if(temp.next == null) {
        System.out.println("链表为空");
        return;
    }
    while(true) {
        if(temp.next == null) {
            break;
        }
        System.out.println(temp.next);
        temp = temp.next;
    }
}

//添加方法，按照no排序添加
public void addByNo(HeroNode heroNode) {
    HeroNode temp = head;
    boolean flag = false; //用于判断no是否重复
    
    while(true) {
        if(temp.next == null) {
            break;
        }
        if(temp.next.no > heroNode.no) {
            break;
        }else if(temp.next.no == heroNode.no) {
            flag = true;
            break;
        }
        temp = temp.next;
    }
    if(flag) {
        System.out.println("编号已存在，无法继续插入");
    }else {
        heroNode.next = temp.next;
        temp.next = heroNode;
    }
}

//修改链表节点数据
public void update(HeroNode newHeroNode) {
    HeroNode temp = head.next;
    if(temp == null) {
        System.out.println("链表为空！");
    }
    boolean flag = false;
    while(true) {
        if(temp == null) {
            break;
        }
        if(temp.no == newHeroNode.no) {
            flag = true;
            break;
        }
        temp = temp.next;
    }
    
    if(flag) {
        temp.name = newHeroNode.name;
        temp.nickname = newHeroNode.nickname;
    }else {
        System.out.println("no不存在");
    }
    
}

//删除节点
public void delete(int no) {
    HeroNode temp = head.next;
    HeroNode temp1 = head;
    if(temp ==null) {
        System.out.println("链表为空");
    }
    boolean flag = false;
    while(true) {
        if(temp ==null) {
            break;
        }
        if(temp.no == no) {
            flag = true;
            break;
        }
        temp = temp.next;
        temp1 = temp1.next;
    }
    if(flag) {
        temp1.next = temp.next;
    }else {
        System.out.println("no不存在");
    }
    }
}

  //定义HeroNode，每个HeroNode对象就是一个节点
class HeroNode{
public int no;
public String name;
public String nickname;
public HeroNode next; //指向下一个节点
public HeroNode(int no,String name,String nickname) {
    this.no = no;
    this.name = name;
    this.nickname = nickname;   
}
//重写toString方法
@Override
public String toString() {
    return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
 }
}

下一节：栈（stack）

https://www.jianshu.com/p/38b6ce825c30