链表-Java实现链表数据结构

骑猪看日落 2023-02-16 06:03 49阅读 0赞

链表通常由一连串节点组成,每个节点包含任意的实例数据(data fields)和一或两个用来指向上 一个/或下一个节点的位置的链接(“links”)

链表(Linked list):是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数 据,而是在每一个节点里存到下一个节点的指针(Pointer)。
使用链表结构可以克服数组需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针
域,空间开销比较大。

单向链表

单链表是链表中结构最简单的。一个单链表的节点(Node)分为两个部分,第一个部分(data)保存或者显示关于节点的信息,另一个部分存储下一个节点的地址。最后一个节点存储地址的部分指向空值。
单向链表只可向一个方向遍历,一般查找一个节点的时候需要从第一个节点开始每次访问下一个节 点,一直访问到需要的位置。而插入一个节点,对于单向链表,我们只提供在链表头插入,只需要将当 前插入的节点设置为头节点,next指向原头节点即可。删除一个节点,我们将该节点的上一个节点的 next指向该节点的下一个节点
在这里插入图片描述
在表头增加节点:
在这里插入图片描述
在表头删除节点:
在这里插入图片描述

  1. /**
  2. * @author shihaowei
  3. * @date 2020-06-03 16:28
  4. */
  5. public class SingleLinkList {
  6. private int size;
  7. private Node head;
  8. public SingleLinkList() {
  9. this.size = 0;
  10. this.head = null;
  11. }
  12. /** 内部类节点 */
  13. public class Node {
  14. private Object data;
  15. private Node next;
  16. public Node(Object data) {
  17. this.data = data;
  18. }
  19. @Override
  20. public String toString() {
  21. return "Node{" +
  22. "data=" + data +
  23. ", next=" + next +
  24. '}';
  25. }
  26. }
  27. /** 添加节点 */
  28. public Object addHead(Object obj){
  29. Node newNode = new Node(obj);
  30. if (size == 0){
  31. head = newNode;
  32. }else {
  33. newNode.next = head;
  34. head = newNode;
  35. }
  36. size++;
  37. return obj;
  38. }
  39. /** 删除头节点 */
  40. public Object delHead(){
  41. if (size > 0){
  42. Object data = head.data;
  43. head = head.next;
  44. size--;
  45. return data;
  46. }
  47. return false;
  48. }
  49. /** 获取指定数据节点*/
  50. public Node find(Object value){
  51. Node current = head;
  52. int tempsize = size;
  53. while (tempsize>0){
  54. if (current.data.equals(value)){
  55. return current;
  56. }else {
  57. current = current.next;
  58. tempsize--;
  59. }
  60. }
  61. return null;
  62. }
  63. /** 删除数据节点*/
  64. public boolean delValue(Object value){
  65. if (size == 0){
  66. return false;
  67. }
  68. Node current = head;
  69. Node prenode = head;
  70. while (!current.data.equals(value)){
  71. if (current.next == null){
  72. return false;
  73. }else {
  74. prenode = current;
  75. current = current.next;
  76. }
  77. }
  78. //如果第一个节点就是要删除的
  79. if (current == head){
  80. head = current.next;
  81. size--;
  82. }else {
  83. prenode.next = current.next;
  84. size--;
  85. }
  86. return true;
  87. }
  88. @Override
  89. public String toString() {
  90. return "SingleLinkList{" +
  91. "size=" + size +
  92. ", head=" + head +
  93. '}';
  94. }
  95. public static void main(String[] args) {
  96. SingleLinkList linkList = new SingleLinkList();
  97. linkList.addHead("a");
  98. linkList.addHead("b");
  99. linkList.addHead("c");
  100. //linkList.delHead();
  101. System.out.println(linkList);
  102. }
  103. }

双端链表

对于单项链表,我们如果想在尾部添加一个节点,那么必须从头部一直遍历到尾部,找到尾节点,然后在尾节点后面插入一个节点。这样操作很麻烦,如果我们在设计链表的时候多个对尾节点的引用,那么会简单很多。
在这里插入图片描述

  1. public class DoublePointLinklist {
  2. private Node head;
  3. private Node tail;
  4. private int size;
  5. // 链表的节点类
  6. private class Node{
  7. private Object data;
  8. private Node next;
  9. public Node(Object data) {
  10. this.data = data;
  11. }
  12. }
  13. public DoublePointLinklist() {
  14. this.head = null;
  15. this.tail = null;
  16. this.size = 0;
  17. }
  18. /**
  19. * 头节点插入
  20. * @param data
  21. * @return
  22. */
  23. public Object addHead(Object data){
  24. Node node = new Node(data);
  25. if (head.next == null){
  26. head = node;
  27. tail = node;
  28. }else {
  29. head.next = head;
  30. head = node;
  31. }
  32. size++;
  33. return data;
  34. }
  35. /**
  36. * 尾节点插入
  37. * @param data
  38. * @return
  39. */
  40. public Object addTail(Object data){
  41. Node node = new Node(data);
  42. if (head.next == null) {
  43. head = node;
  44. tail = node;
  45. }else {
  46. tail.next = tail;
  47. tail = node;
  48. }
  49. size++;
  50. return data;
  51. }
  52. /**
  53. * 删除节点
  54. * @param data
  55. * @return
  56. */
  57. public boolean delNode(Object data){
  58. if ( size == 0){
  59. return false;
  60. }
  61. Node prenode = head;
  62. Node current = head;
  63. while (!head.data.equals(data)){
  64. if (current.next == null){
  65. return false;
  66. }else {
  67. prenode = current;
  68. current = current.next;
  69. }
  70. }
  71. if (current == head){
  72. head = current.next;
  73. }else {
  74. prenode.next = current.next;
  75. }
  76. size--;
  77. return true;
  78. }
  79. }

双向链表

我们知道单向链表只能从一个方向遍历,那么双向链表它可以从两个方向遍历
在这里插入图片描述

  1. package person.shw.datastructure.link;
  2. /**
  3. * @author shihaowei
  4. * @date 2020-06-08 16:39
  5. */
  6. public class TwoWayLinkedList {
  7. private Node head;
  8. private Node tail;
  9. private int size;
  10. /**
  11. * 节点类
  12. */
  13. private class Node{
  14. private Object object;
  15. private Node next;
  16. private Node pre;
  17. public Node(Object object) {
  18. this.object = object;
  19. }
  20. }
  21. public TwoWayLinkedList() {
  22. size = 0;
  23. head = null;
  24. tail = null;
  25. }
  26. /**
  27. * 链表头增加节点
  28. * @param obj
  29. */
  30. public void addHead(Object obj){
  31. Node node = new Node(obj);
  32. if (size == 0){
  33. head = node;
  34. tail = node;
  35. }else {
  36. head.pre = node;
  37. head.next = head;
  38. head = node;
  39. }
  40. size++;
  41. }
  42. /**
  43. * 链表尾添加节点
  44. * @param obj
  45. */
  46. public void addTail(Object obj){
  47. Node node = new Node(obj);
  48. if (size == 0) {
  49. head = node;
  50. tail = node;
  51. }else {
  52. tail.next = node;
  53. node.pre = tail;
  54. tail = node;
  55. }
  56. size++;
  57. }
  58. /**
  59. * 删除头节点
  60. * @return
  61. */
  62. public Object deleteHead(){
  63. Node temp = head;
  64. if (size != 0){
  65. head = head.next;
  66. head.pre = null;
  67. size --;
  68. }
  69. return temp;
  70. }
  71. /**
  72. * 删除尾节点
  73. * @return
  74. */
  75. public Object deleteTail(){
  76. Node temp = tail;
  77. if (size != 0){
  78. tail = tail.pre;
  79. size --;
  80. }
  81. return temp;
  82. }
  83. /**
  84. * 获取节点个数
  85. * @return
  86. */
  87. public int getSize(){
  88. return size;
  89. }
  90. /**
  91. * 显示节点信息
  92. */
  93. public void display(){
  94. if(size >0){
  95. Node node = head;
  96. int tempSize = size;
  97. if(tempSize == 1){
  98. //当前链表只有一个节点
  99. System.out.println("["+node.object+"]");
  100. return; }
  101. while(tempSize>0){
  102. if(node.equals(head)){
  103. System.out.print("["+node.object+"->");
  104. }else if(node.next == null){
  105. System.out.print(node.object+"]");
  106. }else{
  107. System.out.print(node.object+"->");
  108. }
  109. node = node.next;
  110. tempSize--;
  111. }
  112. System.out.println(); }else{
  113. //如果链表一个节点都没有,直接打印[]
  114. System.out.println("[]");
  115. }
  116. }
  117. }

有序链表

前面的链表实现插入数据都是无序的,在有些应用中需要链表中的数据有序,这称为有序链表。
在有序链表中,数据是按照关键值有序排列的。一般在大多数需要使用有序数组的场合也可以使用有序链表。有序链表优于有序数组的地方是插入的速度(因为元素不需要移动),另外链表可以扩展到全部有效的使用内存,而数组只能局限于一个固定的大小中。

  1. public class OrderLinkedList {
  2. private Node head;
  3. private class Node{
  4. private int data;
  5. private Node next;
  6. public Node(int data){
  7. this.data = data;
  8. }
  9. }
  10. public OrderLinkedList(){
  11. head = null;
  12. }
  13. //插入节点,并按照从小打到的顺序排列 public void insert(int value){
  14. Node node = new Node(value);
  15. Node pre = null;
  16. Node current = head;
  17. while(current != null && value > current.data){
  18. pre = current;
  19. current = current.next;
  20. }
  21. if(pre == null){
  22. head = node;
  23. head.next = current;
  24. }else{
  25. pre.next = node;
  26. node.next = current;
  27. }
  28. }
  29. //删除头节点
  30. public void deleteHead(){
  31. head = head.next;
  32. }
  33. public void display(){
  34. Node current = head;
  35. while(current != null){
  36. System.out.print(current.data+" ");
  37. current = current.next;
  38. }
  39. System.out.println("");
  40. }
  41. }

在有序链表中插入和删除某一项最多需要O(N)次比较,平均需要O(N/2)次,因为必须沿着链表上一 步一步走才能找到正确的插入位置,然而可以最快速度删除最值,因为只需要删除表头即可,如果一个 应用需要频繁的存取最小值,且不需要快速的插入,那么有序链表是一个比较好的选择方案。比如优先 级队列可以使用有序链表来实现

总结

上面我们讲了各种链表,每个链表都包括一个LinikedList对象和许多Node对象,LinkedList对象通常 包含头和尾节点的引用,分别指向链表的第一个节点和最后一个节点。而每个节点对象通常包含数据部 分data,以及对上一个节点的引用prev和下一个节点的引用next,只有下一个节点的引用称为单向链 表,两个都有的称为双向链表。next值为null则说明是链表的结尾,如果想找到某个节点,我们必须从 第一个节点开始遍历,不断通过next找到下一个节点,直到找到所需要的。栈和队列都是ADT,可以用 数组来实现,也可以用链表实现

发表评论

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

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

相关阅读