循环链表/双向链表

深藏阁楼爱情的钟 2021-09-23 07:02 565阅读 0赞

Java实现循环链表

  1. /**
  2. * @auther: 巨未
  3. * @DATE: 2019/1/4 0004 20:12
  4. * @Description: 循环链表
  5. */
  6. class ClinkDemo {
  7. class Entry {
  8. int data;
  9. Entry next;
  10. public Entry() {
  11. this.data = -1;
  12. this.next = null;
  13. }
  14. public Entry(int val) {
  15. this.data = val;
  16. this.next = null;
  17. }
  18. }
  19. private Entry head = null;
  20. public ClinkDemo() {
  21. this.head = new Entry();//得到头结点的引用
  22. this.head.next = this.head;
  23. }
  24. /*
  25. *头插法
  26. */
  27. public void insertHead(int val) {
  28. Entry entry = new Entry(val);
  29. entry.next = this.head.next;
  30. this.head.next = entry;
  31. }
  32. /*
  33. *尾插法
  34. */
  35. public void insertTail(int val) {
  36. Entry cur = this.head;
  37. while (cur.next != this.head) {
  38. cur = cur.next;
  39. }
  40. Entry entry = new Entry(val);
  41. cur.next = entry;
  42. entry.next = this.head; //让插入的next域指向头结点的地址
  43. }
  44. /*
  45. *删除所有值为key的节点
  46. */
  47. public void deleteAllkey(int key) {
  48. Entry pre = this.head;
  49. Entry cur = this.head.next;
  50. while (cur != this.head) {
  51. if (cur.data == key) {
  52. pre.next = cur.next;
  53. cur = cur.next;// cur = pre.next;
  54. } else
  55. pre = cur;
  56. cur = cur.next;
  57. }
  58. }
  59. /*
  60. *打印
  61. */
  62. public void show() {
  63. Entry cur = this.head.next;
  64. while (cur != this.head) {
  65. System.out.print(cur.data + " ");
  66. cur = cur.next;
  67. }
  68. System.out.println();
  69. }
  70. }
  71. public class TestCLinkDemo {
  72. public static void main(String[] args) {
  73. ClinkDemo clinkDemo = new ClinkDemo();
  74. for (int i = 0; i < 5; i++) {
  75. clinkDemo.insertHead(i);//头插 倒序
  76. }
  77. clinkDemo.show();
  78. for (int i = 0; i < 5; i++) {
  79. clinkDemo.insertTail(i); //尾插 正序
  80. }
  81. clinkDemo.show();
  82. }
  83. }

Java实现双向链表

  1. /**
  2. * @auther: 巨未
  3. * @DATE: 2019/1/4 0004 20:43
  4. * @Description: 双向链表
  5. */
  6. class DlinkDemo{
  7. class Entry{
  8. int data;
  9. Entry prev;
  10. Entry next;
  11. public Entry() { //
  12. this.data = -1;
  13. this.prev = null;
  14. this.next = null;
  15. }
  16. public Entry(int val) {
  17. this.data = val;
  18. this.prev = null;
  19. this.next = null;
  20. }
  21. }
  22. private Entry head = null;
  23. public DlinkDemo() {
  24. this.head = new Entry();//得到头结点的引用
  25. }
  26. /*
  27. *头插法 *************第一次插入
  28. */
  29. public void insertHead(int val) {
  30. Entry entry = new Entry(val); //插入的节点
  31. entry.next = head.next;
  32. this.head.next = entry;
  33. entry.prev = this.head;
  34. // entry.next.prev = entry; //java.lang.NullPointerException
  35. // entry.next本来就是null,空指针异常
  36. if(entry.next != null) {
  37. entry.next.prev = entry;
  38. }
  39. }
  40. /*
  41. *尾插法
  42. */
  43. public void insertTail(int val) {
  44. Entry cur = this.head;
  45. while (cur.next != null) {
  46. cur = cur.next;
  47. }
  48. Entry entry = new Entry(val);
  49. cur.next = entry;
  50. entry.prev = cur;
  51. }
  52. /*
  53. *打印
  54. */
  55. public void show() {
  56. Entry cur = this.head.next;
  57. while (cur != null) {
  58. System.out.print(cur.data + " ");
  59. cur = cur.next;
  60. }
  61. System.out.println();
  62. }
  63. /*
  64. *删除一个值为Key的节点****************最后一个
  65. */
  66. public void deletekey(int key) {
  67. Entry cur = this.head.next;
  68. while (cur != null) { //遍历双向链表
  69. if(cur.data == key) {
  70. cur.next.prev = cur.prev; //删除节点的后继的前驱为 它的前驱
  71. if (cur.next != null) {
  72. cur.prev.next = cur.next; //删除节点的前驱的后继为 它的后继
  73. } cur = cur.next;
  74. }
  75. }
  76. }
  77. }
  78. public class TestDlinkDemo {
  79. public static void main(String[] args) {
  80. DlinkDemo dlinkDemo = new DlinkDemo();
  81. /* for (int i = 0; i < 5 ; i++) {
  82. dlinkDemo.insertHead(i);
  83. }
  84. dlinkDemo.show();*/
  85. for (int i = 0; i < 5 ; i++) {
  86. dlinkDemo.insertTail(i);
  87. }
  88. dlinkDemo.show();
  89. dlinkDemo.deletekey(1);
  90. }
  91. }

发表评论

表情:
评论列表 (有 0 条评论,565人围观)

还没有评论,来说两句吧...

相关阅读

    相关 循环双向

    一、循环链表 循环链表是与单链表一样,是一种链式的存储结构,所不同的是,循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点,从而构成一个环形的链。

    相关 双向循环

    一、双向链表 每个结点有两个指针域和若干数据域,其中一个指针域指向它的前趋结点,一个指向它的后继结点。它的优点是访问、插入、删除更方便,速度也快了。但“是以空间换时间”。

    相关 双向循环

    双向链表 单链表的一个优点是结构简单,但是它也有一个缺点,即在单链表中只能通过一个结点的引用访问其后续结点,而无法直接访问其前驱结点, 要在单链表中找到某个结点的前驱结点