> 文档中心 > 【数据结构(Java)】链表

【数据结构(Java)】链表

数据结构-Java 链表

  • 线性表
    • 链表
      • 单链表
      • 双向链表
      • 环形链表

线性表

定义:可以在任意位置进行插入和删除操作的、由n个相同类型元素组成的线性结构;线性表每个元素的数据类型都是抽象元素的数据类型。

线性表可以用顺序存储结构和链式存储结构存储;用顺序存储结构实现的线性表称为顺序表,用链式存储结构实现的线性表称作链表。链表主要有单链表、双向链表和环形链表(双向循环链表)。
操作集合:
初始化ListInitiate(L)
求当前元素个数ListLength(L):返回L的元素个数;
插入/删除/取出元素ListInsert(L,i,x)/ListDelete(L,i,x)/ListGet(L,i,下):插入或删除表中第i个元素

链表

节点:由一个元素域(data)及若干个指针域(next)组成的结构体
分为带头节点和不带头节点

单链表

定义:除first和last元素外,每个元素只有一个前驱元素和一个后继元素。

节点:一个元素域及一个或若干个指针域组成的结构体。
1)链表是以节点的方式来存储
2)每个节点包含data域:存放数据;next域:指向下一个节点.
3)链表的各个节点不一定是连续存储,而是通过next域的指向来连接的
4)链表分带头节点的链表和不带头节点的链表,根据实际的需求来确定(一般为带头节点)

public class SingleLinkedListDemo {    public static void main(String[] args) { SingleLinkedList s = new SingleLinkedList(); HeroNode h1 = new HeroNode(1, "1", "01"); HeroNode h2 = new HeroNode(2, "2", "02"); HeroNode h3 = new HeroNode(3, "3", "03"); s.add(h1); s.add(h2); s.add(h3); s.list(); s.del(2); s.list(); HeroNode n1 = new HeroNode(1, "01", "001"); s.update(n1); s.list(); System.out.println(s.getLength(s.getHead())); HeroNode r = s.find(s.getHead(), 2); System.out.println(r); s.reverseList(s.getHead()); s.list();    }}//单链表类class SingleLinkedList {    private HeroNode head = new HeroNode(0, "", "");    private HeroNode Head;    public HeroNode getHead() { return head;    }//增加节点    public void add(HeroNode heroNode) { HeroNode temp = head;//定义一个temp指针指向链表的头节点 while (true) {     if (temp.next == null) {  break;//当指针temp的next指向null时说明到了链表的最后     }     temp = temp.next;//指向下一个节点 } temp.next = heroNode;    }//查看链表    public void list() { if (head.next == null) {     System.out.println("空");//判断链表是否为空,头节点的next为空则为空链表 } HeroNode temp = head.next; while (true) {     if (temp == null) {  break;     }     System.out.println(temp);     temp = temp.next; }    }//删除节点    public void del(int no) { HeroNode temp = head.next; while (true) {     if (temp == null) {  break;     } else if (temp.next.no == no) {//  temp.next = temp.next.next;  System.out.println("删除成功");  break;     }     temp = temp.next; }    }//更改节点信息    public void update(HeroNode newHeroNode) { HeroNode temp = head.next; while (true) {     if (temp.next == null) {  break;     } else if (temp.no == newHeroNode.no) {  temp.name = newHeroNode.name;  temp.nickname = newHeroNode.nickname;  System.out.println("修改成功");  break;     } else System.out.printf("无该no");     temp = temp.next; }    }//获取链表长度    public int getLength(HeroNode head) { if (head.next == null) {     return 0; } int length = 0; while (head.next != null) {     length++;     head = head.next; } return length;    }    public void reverseList(HeroNode head){ if(head.next == null || head.next.next == null){     return; } HeroNode cur =head.next; HeroNode next ; HeroNode reverseHead = new HeroNode(0,"",""); while (cur != null){     next = cur;     reverseHead.next = next;     cur = cur.next; } head.next = reverseHead.next;    }//查找指定序号节点    public HeroNode find(HeroNode h, int no) { int l = getLength(head); if (no <= 0 &&  no > l) {     return null; } HeroNode temp = head.next; for (int i = 0; i < l-no; i++) {     temp = temp.next; } return temp;    }}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;    }    public String toString() { return "HeroNode[no = " + no + ",name=" + name + ",nickname= " + nickname + "]"; //重写toString方法返回属性    }}

双向链表

定义:每个节点除了后继指针外还有一个前驱指针域pre,指向前一个节点

实现思路:
1)遍历方和单链表一样,只是可以向前,也可以向后查找
2)添加(默认添加到双向链表的最后)
(1)先找到双向链表的最后这个节点
(2)temp.next =newHeroNode
(3)newHeroNode.pre =temp;
3)修改思路和原理的单向链表一样.
4)删除
(1)因为是双向链表,因此,我们可以实现自我删除某个节点
(2)直接找到要删除的这个节点,比如temp
(3)temp.pre.next =temp.next
(4)temp.next.pre=temp.pre;

package work1.sjjg.linkedlist;public class DoubleLinkedList {    public static void main(String[] args) { HeroNode2 heroNode2 = new HeroNode2(1, "01", "001"); DoubleLinkedList doubleLinkedList = new DoubleLinkedList(); HeroNode2 h1 = new HeroNode2(1, "1", "01"); HeroNode2 h2 = new HeroNode2(2, "2", "02"); HeroNode2 h3 = new HeroNode2(3, "3", "03"); doubleLinkedList.add(h1); doubleLinkedList.add(h2); doubleLinkedList.add(h3); doubleLinkedList.list(); doubleLinkedList.del(2); doubleLinkedList.list(); HeroNode n1 = new HeroNode(1, "01", "001"); doubleLinkedList.update(n1); doubleLinkedList.list();// System.out.println(doubleLinkedList.getLength(doubleLinkedList.getHead()));    }    private HeroNode2 head = new HeroNode2(0, "", "");    private HeroNode2 Head;    public HeroNode2 getHead() { return head;    }    public void add(HeroNode2 heroNode) { HeroNode2 temp = head; while (true) {     if (temp.next == null) {  break;     }     temp = temp.next; } temp.next = heroNode; heroNode.pre = temp;    }    public void list() { if (head.next == null) {     System.out.println("空"); } HeroNode2 temp = head.next; while (true) {     if (temp == null) {  break;     }     System.out.println(temp);     temp = temp.next; }    }    public void del(int no) { HeroNode2 temp = head.next; while (true) {     if (temp == null) {  break;     } else if (temp.no == no) {  temp.pre.next = temp.next;  temp.next.pre = temp.pre;  System.out.println("删除成功");  break;     }     temp = temp.next; }    }    public void update(HeroNode newHeroNode) { HeroNode2 temp = head.next; while (true) {     if (temp.next == null) {  break;     } else if (temp.no == newHeroNode.no) {  temp.name = newHeroNode.name;  temp.nickname = newHeroNode.nickname;  System.out.println("修改成功");  break;     } else System.out.printf("无该no");     temp = temp.next; }    }    public int getLength(HeroNode head) { if (head.next == null) {     return 0; } int length = 0; while (head.next != null) {     length++;     head = head.next; } return length;    }}class HeroNode2 {    public int no;    public String name;    public String nickname;    public HeroNode2 next;    public HeroNode2 pre;    public HeroNode2(int no, String name, String nickname) { this.no = no; this.name = name; this.nickname = nickname;    }    public String toString() { return "HeroNode[no = " + no + ",name=" + name + ",nickname= " + nickname + "]";    }}

环形链表

环形链表顾名思义就是各个节点相连成环
我们带入约瑟夫问题中去了解环形链表,约瑟夫问题:有n个小孩围坐成一圈,随机从一个小孩开始逆时针报数,当报到指定数x的小孩出圈,下一个小孩再从1开始报数,直到圈中小孩数小于x.
实现思路:
1.先创建第一个节点,让fist指向该节点,并形成环形
2.后面当我们每创建一个新的节点,就把该节点,加入到已有的环形链表中即可

遍历环形链表
1.先让一个辅助指针(变量)curBoy,指向first节点
2.然后通过一个while循环遍历该环形链表即可curBoy.next==first结束

package work1.sjjg.linkedlist;public class Josefu {    public static void main(String[] args) { CircleLinkedList circleLinkedList = new CircleLinkedList(); circleLinkedList.add(125); circleLinkedList.list(); circleLinkedList.countBoy(10,20,125);    }}class CircleLinkedList {    private Boy first = new Boy(1);    public void add(int n) { if (n < 2) {     System.out.printf("n不正确");     return; } Boy cur = null; ; for (int i = 1; i < n; i++) {     Boy boy = new Boy(i);     if (i == 1) {  first = boy;  first.setNext(first);  cur = first;     } else {  cur.setNext(boy);  boy.setNext(first);  cur = boy;     } }    }    public void list() { if (first == null) {     return; } Boy curboy = first; while (true) {     System.out.println("no=" + curboy.getNext());     curboy = curboy.getNext();     if (curboy == first) {  break;     } }    }    public void countBoy(int nums, int countNum, int startNo) { if (first == null || nums < 1 || startNo > nums) {     System.out.println("输入有误"); } Boy temp = first; while (true){     if(temp.getNext() == first){  break;     }     for (int j = 0; j < startNo - 1; j++) {  first = first.getNext();  temp = temp.getNext();     } } while (true) {     if (temp == first) {  break;     }     for (int i = 0; i < countNum - 1; i++) {  first = first.getNext();  temp = temp.getNext();     }     System.out.println("no:" + first.getNo());     first = first.getNext();     temp.setNext(first); }    }}class Boy {    private int no;    private Boy next;    public Boy(int no) { this.no = no;    }    public int getNo() { return no;    }    public void setNo(int no) { this.no = no;    }    public Boy getNext() { return next;    }    public void setNext(Boy next) { this.next = next;    }}