【数据结构(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; }}