链表

链表基础

单向链表

　　单向链表包括两部分，第一部分是节点中包含的内容，第二部分是这个节点的下一个节点的地址值。

　　模拟一个单链表

/**
 * 单向链表的节点
 */
public class SingleNode {
    private User user;
    private SingleNode next;

    public SingleNode(User user, SingleNode next) {
        this.user = user;
        this.next = next;
    }

    public SingleNode() {
    }

    public User getUser() {
        return user;
    }

    public void setUser(User user) {
        this.user = user;
    }

    public SingleNode getNext() {
        return next;
    }

    public void setNext(SingleNode next) {
        this.next = next;
    }

 1 /**
 2  * 节点中的数据
 3  */
 4 public class User {
 5     private int index;//人物排名
 6     private String name;//人物姓名
 7     private String sex;//人物性别
 8     private int age;//人物年龄
 9 
10     public int getIndex() {
11         return index;
12     }
13 
14     public void setIndex(int index) {
15         this.index = index;
16     }
17 
18     public String getName() {
19         return name;
20     }
21 
22     public void setName(String name) {
23         this.name = name;
24     }
25 
26     public String getSex() {
27         return sex;
28     }
29 
30     public void setSex(String sex) {
31         this.sex = sex;
32     }
33 
34     public int getAge() {
35         return age;
36     }
37 
38     public void setAge(int age) {
39         this.age = age;
40     }
41 
42     public User(int index, String name, String sex, int age) {
43         this.index = index;
44         this.name = name;
45         this.sex = sex;
46         this.age = age;
47     }
48 
49     public User() {
50     }

 1 /**
 2  * 单链表的方法
 3  */
 4 public class SingleLinkedList {
 5     private SingleNode head = new SingleNode(null, null);//单链表的头结点
 6 
 7     //添加数据到链表尾端
 8     public void addIntoLinkedList(User user) {
 9         SingleNode next = new SingleNode(user, null);
10         SingleNode temp = this.head;
11         while (temp.getNext() != null) {
12             temp = temp.getNext();
13         }
14         //表示到了链表的尾端
15         temp.setNext(next);
16     }
17 
18     //按照人物排名大小添加至链表(由小至大)
19     public void addByIndex(User user) {
20         int index = user.getIndex();//需要添加的人物排名
21         SingleNode next = new SingleNode(user, null);
22         SingleNode temp = this.head;
23         temp.setUser(new User(-1, null, null, 0));//设置初始排名为-1
24         while (true) {
25             //到达链表的尾端
26             if (temp.getNext() == null) {
27                 temp.setNext(next);
28                 break;
29             }
30             if (temp.getNext().getUser().getIndex() >= index) {
31                 next.setNext(temp.getNext());
32                 temp.setNext(next);
33                 break;
34             }
35             temp = temp.getNext();
36         }
37     }
38 
39     //遍历链表
40     public void showLinkedList() {
41         int index=1;
42         SingleNode temp = this.head.getNext();
43         while (true){
44             if (temp==null){
45                 System.out.printf("遍历完成,一共有%d个用户",index);
46                 break;
47             }
48             System.out.printf("第%d位人物"+temp.getUser().getName(),temp.getUser().getIndex());
49             temp=temp.getNext();
50             System.out.println();
51             index++;
52         }
53     }

 1 /**
 2  * 测试单链表
 3  */
 4 public class TestSingleLinkedList {
 5     public static void main(String[] args) {
 6         //按顺序的链表
 7         SingleLinkedList indexLinkedList=new SingleLinkedList();
 8         //不安循序的链表
 9         SingleLinkedList noIndexLinkedList=new SingleLinkedList();
10 
11         Random r=new Random();
12         //循环创建随机用户
13         for (int i = 0; i < 10; i++) {
14             int index =r.nextInt(10);
15             User user=new User(index,"第"+i+"个用户","男",i);
16             indexLinkedList.addByIndex(user);
17             noIndexLinkedList.addIntoLinkedList(user);
18 
19         }
20         System.out.println("有序的链表开始遍历....");
21         indexLinkedList.showLinkedList();
22         System.out.println("无序的链表开始遍历....");
23         noIndexLinkedList.showLinkedList();
24     }

至此完成了单链表的简单理解和手动实现。