数据结构

数据结构与算法

数据结构

什么是数据结构

数据结构是计算机存储、组织数据的方式，包含线性结构、树形结构、图形结构。

线性表

线性表是具有n个相同类型元素的有限序列

• a1是首节点，an是尾结点
• a1是a2的前驱，a2是a1的后继

常见的线性表有数组、链表、栈、队列、哈希表

数组

数组是一种顺序存储的线性表，所有元素的内存地址是连续的

int[] array = new int[]{11,22,33}

由于编程语言中数组是固定容量的，因此我们可以实现动态数组。

动态数组的设计

int size();// 元素的数量

boolean isEmpty();// 是否为空

boolean contains(E element);// 是否包含某个元素

void add(E element);// 添加元素到最后面

E get(intindex);// 返回index位置对应的元素

E set(intindex, E element);// 设置index位置的元素

void add(intindex, E element);// 往index位置添加元素

E remove(intindex);// 删除index位置对应的元素

int indexOf(E element);// 查看元素的位置

void clear();// 清除所有元素

链表（Linked List）

动态数组有明显的缺点，可能会造成内存空间的大量浪费

链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的。

Leetcode 题目

1. 237. 删除链表中的节点

   #思路：直接将当前节点的下一个节点的值替换当前节点的值，当前节点的下一个节点指向的节点替换当前节点的下一个节点
   public void deleteNode(ListNode node) {
         node.val=node.next.val;
         node.next=node.next.next;
   }
   

2. 206. 反转链表

   #递归
   public ListNode reverseList(ListNode head) {
          if (head==null || head.next==null) return head;
          ListNode newNode=reverseList(head.next);
          head.next.next=head;
          head.next=null;
          return newNode;
      }#迭代
   public ListNode reverseList(ListNode head) {
          ListNode newNode=null;
          while (head!=null){
              ListNode temp=head.next;
              head.next=newNode;
              newNode=head;
              head=temp;
          }
          return newNode;
      }
   

3. 141. 环形链表

   #思路：使用快慢指针
   假想「乌龟」和「兔子」在链表上移动，「兔子」跑得快，「乌龟」跑得慢。
   当「乌龟」和「兔子」从链表上的同一个节点开始移动时，如果该链表中没有环，
   那么「兔子」将一直处于「乌龟」的前方；如果该链表中有环，那么「兔子」会先于「乌龟」进入环，并且一直在环内移动。
   等到「乌龟」进入环时，由于「兔子」的速度快，它一定会在某个时刻与乌龟相遇，即套了「乌龟」若干圈。
   我们可以根据上述思路来解决本题。具体地，我们定义两个指针，一快一满。
   慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，而快指针在位置 head.next。
   这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。
   否则快指针将到达链表尾部，该链表不为环形链表。
   public boolean hasCycle(ListNode head) {
              if (head == null || head.next == null) return false;           
   	   ListNode slow = head;
              ListNode fast = head.next;
              while (fast != null && fast.next != null) {
                  if (fast == slow) return true;
                  slow = slow.next;
                  fast = fast.next.next;
              }
              return false;       }