数据结构~05.双链表的操作,手写Java语言中的LinkedList集合

爱被打了一巴掌 2023-02-28 08:45 58阅读 0赞

数据结构~05.双链表的操作,手写LinkedList集合

本文是上一篇文章的后续,详情点击该链接~

先写一个普通的双链表插入和遍历~

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. typedef struct no_de { 
  4.     int data;                //data中存放数据域
  5.     struct no_de* pre;        //指向前驱结点的指针
  6.     struct no_de* next;        //指向后继结点的指针
  7. }Node;
  8. //建立头节点
  9. Node* getHead() { 
  10.     Node* head = (Node*)malloc(sizeof(Node));
  11.     head->data = NULL;
  12.     head->next = NULL;
  13.     head->pre = NULL;
  14.     return head;
  15. }
  16. //插入操作
  17. void Insert(Node *L,int data) { 
  18.     Node* p = (Node*)malloc(sizeof(Node));
  19.     p->data = data;
  20.     p->next = L->next;
  21.     p->pre = L;
  22.     L->next = p;
  23. }
  24. //遍历链表
  25. void Print(Node *L) { 
  26.     Node* p = L->next;
  27.     //如果链表为空就输出[]
  28.     if (p == NULL) { 
  29.         printf("[]");
  30.     }
  31.     //遍历链表
  32.     while (p != NULL) { 
  33.         //判断是否到了最后
  34.         if (p ->next != NULL) { 
  35.             printf("%d->",p->data);
  36.         }
  37.         else { 
  38.             printf("%d",p->data);
  39.         }
  40.         p = p->next;
  41.     }
  42. }
  43. int main(int argc,char * argv[]) { 
  44.     Node* list = getHead();
  45.     Insert(list,1); Insert(list, 2); Insert(list, 3); Insert(list, 4);
  46.     Print(list);
  47.     getchar();
  48.     return 0;
  49. }

删除结点的算法

  1. //在单链表的基础上做了稍稍修改~
  2.     q = p->next;
  3.     p->next = q->next;
  4.     q->next->pre = p;
  5.     free(q);

查找结点的算法

  1. Node* findNode(Node *C, int x) { 
  2.     Node* p = C->next;
  3.     while (p != NULL) { 
  4.         if (p ->data == x) { 
  5.             break;
  6.         }
  7.         p = p->next;
  8.     }
  9.     return p;
  10. }

奉上完整代码

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. typedef struct no_de { 
  4.     int data;                //data中存放数据域
  5.     struct no_de* pre;        //指向前驱结点的指针
  6.     struct no_de* next;        //指向后继结点的指针
  7. }Node;
  8. //建立头节点
  9. Node* getHead() { 
  10.     Node* head = (Node*)malloc(sizeof(Node));
  11.     head->data = NULL;
  12.     head->next = NULL;
  13.     head->pre = NULL;
  14.     return head;
  15. }
  16. //插入操作
  17. void Insert(Node *L,int data) { 
  18.     Node* p = (Node*)malloc(sizeof(Node));
  19.     p->data = data;
  20.     p->next = L->next;
  21.     p->pre = L;
  22.     L->next = p;
  23. }
  24. //删除操作
  25. int Delete(Node* C, int s) { 
  26.     Node* p, * q;
  27.     p = C;
  28.     //开始查找
  29.     while (p->next != NULL) { 
  30.         if (p->next->data == s) { 
  31.             break;
  32.         }
  33.         p = p->next;
  34.     }
  35.     if (p->next == NULL) { 
  36.         return 0;
  37.     }
  38.     else { 
  39.         //开始删除
  40.         q = p->next;
  41.         p->next = q->next;
  42.         q->next->pre = p;
  43.         free(q);
  44.         return 1;
  45.     }
  46. }
  47. //遍历链表
  48. void Print(Node *L) { 
  49.     Node* p = L->next;
  50.     //如果链表为空就输出[]
  51.     if (p == NULL) { 
  52.         printf("[]");
  53.     }
  54.     //遍历链表
  55.     while (p != NULL) { 
  56.         //判断是否到了最后
  57.         if (p ->next != NULL) { 
  58.             printf("%d->",p->data);
  59.         }
  60.         else { 
  61.             printf("%d",p->data);
  62.         }
  63.         p = p->next;
  64.     }
  65.     printf("\n");
  66. }
  67. //查找结点
  68. Node* findNode(Node *C, int x) { 
  69.     Node* p = C->next;
  70.     while (p != NULL) { 
  71.         if (p ->data == x) { 
  72.             break;
  73.         }
  74.         p = p->next;
  75.     }
  76.     return p;
  77. }
  78. int main(int argc,char * argv[]) { 
  79.     Node* list = getHead();
  80.     Insert(list,1); Insert(list, 2); Insert(list, 3); Insert(list, 4);
  81.     Delete(list,2);
  82.     Print(list);
  83.     Node* p = findNode(list,3);
  84.     printf("%d",p->data);
  85.     getchar();
  86.     return 0;
  87. }

采用尾插法建立双链表?

  1. void InsertLast(Node*& L, int a[], int n) { 
  2.     Node* s, * r;
  3.     int i;
  4.     L = (Node*)malloc(sizeof(Node));
  5.     L->pre = NULL;
  6.     L->next = NULL;
  7.     //这里和单链表一样, r始终指向终端结点
  8.     r = L;
  9.     for (i = 0; i < n; ++i) { 
  10.         //建立新结点
  11.         s = (Node*)malloc(sizeof(Node));
  12.         s->data = a[i];
  13.         //将s 插入到 L的尾部，并且r 指向 s
  14.         r->next = s;
  15.         s->pre = r;
  16.         r = s;
  17.     }
  18.     r->next = NULL;
  19. }

Java中的LinkedList

定义List接口

  1. public interface List <E>{ 
  2.     int size();
  3.     boolean isEmpty();
  4.     boolean contains(E element);
  5.     void add(E element);
  6.     E get(int index);
  7.     E set(int index,E element);
  8.     void add(int index,E element);
  9.     E remove(int index);
  10.     int indexOf(E element);
  11.     void clear();
  12.     String toString();
  13. }

接口实现

  1. public class LinkedList<E> implements List<E>{ 
  3.     private int size;   //集合的长度
  4.     private Node first;
  5.     private Node last;
  7.     @Override
  8.     public int size() { 
  9.         return size;
  10.     }
  12.     //判断当前集合中是否有元素
  13.     @Override
  14.     public boolean isEmpty() { 
  15.         return size == 0;
  16.     }
  18.     //判断当前元素是否存在
  19.     @Override
  20.     public boolean contains(E element) { 
  21.         return indexOf(element) > -1;
  22.     }
  24.     @Override
  25.     public void add(E element) { 
  26.         //调用下面的add方法,根据size保证每次都添加在最后
  27.         add(size,element);
  28.     }
  29.     //取得坐标位置上的节点
  30.     private Node<E> node(int index){ 
  31.         Node N = first; //指向头
  32.         //先判断要查找的index,是靠近头还是靠近尾
  33.         //如果靠近头就从头开始查找,如果靠近尾就从尾开始查找
  34.         //方法: 根据index 和 size的一半去比较
  35.         if(index > (size >> 1)){ 
  36.             //靠近尾
  37.             N = last;   //指向尾
  38.             for(int i = size-1; i > index; i--){ 
  39.                 N = N.pre;
  40.             }
  41.         }else{ 
  42.             //靠近头
  43.             for(int i = 0; i < index; i++){ 
  44.                 N = N.next;
  45.             }
  46.         }
  47.         return N;
  48.     }
  50.     @Override
  51.     public E get(int index) { 
  52.         //防止坐标越界
  53.         if(index < 0 || index >= size){ 
  54.             throw  new IndexOutOfBoundsException("index： " + index + " size: " + size);
  55.         }
  56.         //调用方法
  57.         return node(index).element;
  58.     }
  60.     @Override
  61.     public E set(int index, E element) { 
  62.         //获得index上的node
  63.         Node<E> node = node(index);
  64.         //保存原来的值
  65.         E oldElement = node.element;
  66.         //新值覆盖老值
  67.         node.element = element;
  68.         //返回老值
  69.         return oldElement;
  70.     }
  72.     @Override
  73.     public void add(int index, E element) { 
  74.         //当需要添加到末尾时
  75.         if(index == size) { 
  76.             //拿到last节点
  77.             Node l = last;
  78.             //构建node 完成指向关系
  79.             Node newNode = new Node(l,null,element);
  80.             //将原来的last 节点的next 修改成新构建出来的node
  81.             last = newNode;
  82.             if(l == null){ 
  83.                 first = newNode;
  84.             }else { 
  85.                 l.next = newNode;
  86.             }
  87.         }else{ 
  88.             //获得指定的index
  89.             Node<E> node = node(index);
  90.             //获得前一个结点
  91.             Node<E> pre = node.pre;
  92.             //构建新的now 完成指向关系
  93.             Node<E> newNode = new Node(pre, node, element);
  94.             //改变指向
  95.             pre.next = newNode;
  96.             if (pre == null) { 
  97.                 first = newNode;
  98.             } else { 
  99.                 node.pre = newNode;
  100.             }
  101.         }
  102.         size++;
  103.     }
  105.     //链表删除的主要原理就是将被删除者的前一个元素指向后一个元素
  106.     //比如 A->B->C 当我要删除B的时候,就让A -> C
  107.     @Override
  108.     public E remove(int index) { 
  109.         //防止坐标越界
  110.         if(index < 0 || index >= size){ 
  111.             throw  new IndexOutOfBoundsException("index： " + index + " size: " + size);
  112.         }
  113.         //获得要删除的元素Node
  114.         Node<E>node = node(index);
  115.         //获得前一个结点
  116.         Node<E> pre = node.pre;
  117.         //获得后一个结点
  118.         Node<E> next = node.next;
  120.         if(pre == null){ 
  121.             //firest进行修改
  122.             first = next;
  123.             next.pre = null;
  124.         }else{ 
  125.             //改变前一个结点的next
  126.             pre.next = next;
  127.         }
  129.         if(next == null){ 
  130.             //last进行修改
  131.             last = pre;
  132.         }else{ 
  133.             next.pre = pre;
  134.         }
  135.         size--;
  136.         //返回老元素
  137.         return node.element;
  138.     }
  140.     @Override
  141.     public int indexOf(E element) { 
  142.         //查找element元素是否存在,有返回索引,没有返回-1
  143.         Node N = first;
  144.         int index = 0;
  145.         //遍历
  146.         for(Node i = N; i != null; i = i.next){ 
  147.             if(element == i.element){ 
  148.                 return index;
  149.             }
  150.             index++;
  151.         }
  152.         return -1;
  153.     }
  155.     @Override
  156.     public void clear() { 
  157.         size = 0;
  158.         first = null;
  159.         last = null;
  160.     }
  162.     public String toString(){ 
  163.         Node N = first;
  164.         StringBuilder stringBuilder = new StringBuilder("[");
  165.         boolean flag = false;   //判断是否循环到了最后
  166.         for(Node i = N; i != null; i = i.next){ 
  167.             //说明已经到了最后一个元素
  168.             if(i.next == null) { 
  169.                 flag = true;
  170.             }
  171.             //如果没到最后就加 逗号
  172.             if(flag == false){ 
  173.                 stringBuilder.append(i.element + ",");
  174.             }else{   //到了最后就不加逗号
  175.                 stringBuilder.append(i.element);
  176.             }
  177.         }
  178.         stringBuilder.append("]");
  179.         return stringBuilder.toString();
  180.     }
  182.     //内部Node节点类
  183.     private static class Node<E>{ 
  184.         Node<E> pre;
  185.         Node<E> next;
  186.         E element;
  187.         public Node(Node next,E element){ 
  188.             this.next = next;
  189.             this.element = element;
  190.         }
  192.         public Node(Node pre,Node next,E element){ 
  193.             this.pre = pre;
  194.             this.next = next;
  195.             this.element = element;
  196.         }
  198.         public Node() { 
  200.         }
  201.     }
  202. }

发表评论

表情：
评论列表 （有 0 条评论，58人围观）

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

相关阅读

    相关 Java中双链表的操作

    Java中双链表的操作 1. 双链表根据内容添加结点 2. 双链表根据内容删除结点 3. 双链表根据内容修改（新内容替换旧内容） 4. 双链表根据内容查找结点索引

    绝地灬酷狼绝地灬酷狼/ 0 赞/ 52 阅读