本文共 13407 字，大约阅读时间需要 44 分钟。

• 集合：数据元素之间只有“同属于一个集合”关系。
• 线性结构：数据元素之间存在一个对一个的关系。
• 树形结构：数据元素之间存在一个对多个的关系。
• 图状结构或网状结构：数据元素之间存在多个对多个的关系。

对于数据不同的逻辑结构，计算机在物理磁盘上通常有2种物理存储结构：

• 顺序存储结构；
• 链式存储结构。

1.线性表概述

对于常用数据结构，可以将其简单地分为线性结构和非线性结构，其中线性结构主要是线性表，而非线性结构则主要是树和图。

1.1 插入

1.2 删除

public class SequenceList
   
         {
              private final int DEFAULT_SIZE = 16;            //保存数组的长度           private int capacity;           //定义一个数组用于保存顺序线性表的元素           private Object[] elementData;           //保存顺序表中元素的当前个数           private int size = 0;           //以默认数组长度创建空顺序线性表           public SequenceList()           {
                    capacity = DEFAULT_SIZE;                 elementData = new Object[capacity];           }           //以一个初始化元素创建顺序线性表           public SequenceList(T element)           {
                    this();                 elementData[0] = element;                 size++;           }           /**            * 以指定长度的数组来创建顺序线性表            * @param element 指定顺序线性表中第一个元素            * @param initSize 指定顺序线性表底层数组的长度            */           public SequenceList(T element , int initSize)           {
                    capacity = 1;                 //把capacity设为大于initSize的最小的2的n次方                 while (capacity < initSize)                 {
                          capacity <<= 1;                 }                 elementData = new Object[capacity];                 elementData[0] = element;                 size++;           }           //获取顺序线性表的大小           public int length()           {
                    return size;           }           //获取顺序线性表中索引为i处的元素           public T get(int i)           {
                    if (i < 0 || i > size - 1)                 {
                            throw new IndexOutOfBoundsException("线性表索引越界");                 }                 return (T)elementData[i];           }           //查找顺序线性表中指定元素的索引           public int locate(T element)           {
                    for (int i = 0 ; i < size ; i++)                 {
                            if (elementData[i].equals(element))                       {
                                    return i;                       }                 }                 return -1;           }           //向顺序线性表的指定位置插入一个元素           public void insert(T element , int index)           {
                    if (index < 0 || index > size)                    {
                          throw new IndexOutOfBoundsException("线性表索引越界");                 }                 ensureCapacity(size + 1);                 //将指定索引处之后的所有元素向后移动一格                 System.arraycopy(elementData , index , elementData                        , index + 1 , size - index);                 elementData[index] = element;                 size++;           }           //在线性顺序表的开始处添加一个元素           public void add(T element)           {
                    insert(element , size);           }           //很麻烦，而且性能很差           private void ensureCapacity(int minCapacity)           {
                    //如果数组的原有长度小于目前所需的长度                 if (minCapacity > capacity)                 {
                          //不断地将capacity * 2，直到capacity大于minCapacity                        while (capacity < minCapacity)                       {
                                capacity <<= 1;                       }                       elementData = Arrays.copyOf(elementData , capacity);                 }           }           //删除顺序线性表中指定索引处的元素           public T delete(int index)           {
                    if (index < 0 || index > size - 1)                 {
                           throw new IndexOutOfBoundsException("线性表索引越界");                 }                 T oldValue = (T)elementData[index];                 int numMoved = size - index - 1;                 if (numMoved > 0)                 {
                           System.arraycopy(elementData , index+1                             , elementData, index ,       numMoved);                 }                 //清空最后一个元素                 elementData[--size] = null;                  return oldValue;           }           //删除顺序线性表中最后一个元素         public T remove()           {
                    return delete(size - 1);           }           //判断顺序线性表是否为空表           public boolean empty()           {
                    return size == 0;           }           //清空线性表           public void clear()           {
                    //将底层数组所有元素赋为null                 Arrays.fill(elementData , null);                 size = 0;           }           public String toString()           {
                    if (size == 0)                 {
                          return "[]";                 }                 else                 {
                          StringBuilder sb = new StringBuilder("[");                       for (int i = 0 ; i < size ; i++ )                       {
                                sb.append(elementData[i].toString() + ", ");                       }                       int len = sb.length();                       return sb.delete(len - 2 , len).append("]").toString();                 }           }     }
   

2. 链式存储结构

2.1 单链

2.2 双向链表

2.2.1 双向链表的查找

由于双向链表既可从header节点开始依次向后搜索每个节点，也可从tail节点开始，依次向前搜索每个节点，因此当程序试图从双向链表中搜索指定索引处的节点时，既可从该链表的header节点开始搜索，也可从该链表的tail节点开始搜索。至于到底应该从header开始搜索，还是应该从tail开始搜索，则取决于被搜索节点是更靠近header，还是更靠近tail。

一般来说，可以通过被搜索index的值来判断它更靠近header，还是更靠近tail。如果index<size/2，可判断该位置更靠近header，应从header开始搜索；反之，则可判断该位置更靠近tail，那就应从tail开始搜索。

2.2.2 双向链表的插入

双向链表的插入操作更复杂，向双向链表中插入一个新节点必须同时修改两个方向的指针（即引用）

2.2.3 双向链表的删除

双向链表中，删除一个节点也需要同时修改两个方向的指针，双向链表中删除节点的操作

public class DuLinkList
   
         {
              //定义一个内部类Node，Node实例代表链表的节点           private class Node           {
                    //保存节点的数据                 private T data;                 //指向上个节点的引用                 private Node prev;                 //指向下个节点的引用                 private Node next;                 //无参数的构造器                 public Node()                 {
                    }                 //初始化全部属性的构造器                 public Node(T data , Node prev , Node next)                 {
                          this.data = data;                       this.prev = prev;                       this.next = next;                 }           }           //保存该链表的头节点           private Node header;           //保存该链表的尾节点           private Node tail;           //保存该链表中已包含的节点数           private int size;           //创建空链表           public DuLinkList()           {
                    //空链表，header和tail都是null                 header = null;                 tail = null;           }           //以指定数据元素来创建链表，该链表只有一个元素           public DuLinkList(T element)           {
                    header = new Node(element , null , null);                 //只有一个节点，header、tail都指向该节点                 tail = header;                 size++;           }           //返回链表的长度           public int length()           {
                    return size;           }           //获取链式线性表中索引为index处的元素           public T get(int index)           {
                    return getNodeByIndex(index).data;           }           //根据索引index获取指定位置的节点           private Node getNodeByIndex(int index)           {
                    if (index < 0 || index > size - 1)                 {
                            throw new IndexOutOfBoundsException("线性表索引越界");                 }                 if (index <= size / 2)                 {
                            //从header节点开始                         Node current = header;                         for (int i = 0 ; i <= size / 2 && current != null                               ; i++ , current = current.next)                         {
                                  if (i == index)                               {
                                        return current;                             }                                  {
                                  //获取插入点的前一个节点                               Node prev = getNodeByIndex(index - 1);                               //获取插入点的节点                               Node next = prev.next;                               //让新节点的next引用指向next节点，prev引用指向prev节点                               Node newNode = new Node(element , prev , next);                               //让prev的next指向新节点                               prev.next = newNode;                               //让prev的下一个节点的prev指向新节点                               next.prev = newNode;                             size++;                       }                 }           }           //采用尾插法为链表添加新节点           public void add(T element)           {
                    //如果该链表还是空链表                 if (header == null)                 {
                          header = new Node(element , null , null);                       //只有一个节点，header、tail都指向该节点                       tail = header;                 }                 else                 {
                          //创建新节点,新节点的pre指向原tail节点                       Node newNode = new Node(element , tail , null);                       //让尾节点的next指向新增的节点                       tail.next = newNode;                       //以新节点作为新的尾节点                       tail = newNode;                 }                 size++;           }           //采用头插法为链表添加新节点           public void addAtHeader(T element)           {
                    //创建新节点，让新节点的next指向原来的header                 //并以新节点作为新的header                 header = new Node(element , null , header);                 //如果插入之前是空链表                 if (tail == null)                 {
                             tail = header;                 }                 size++;           }           //删除链式线性表中指定索引处的元素           public T delete(int index)           {
                    if (index < 0 || index > size - 1)                 {
                           throw new IndexOutOfBoundsException("线性表索引越界");                 }                 Node del = null;                 //如果被删除的是header节点                 if (index == 0)                 {
                           del = header;                        header = header.next;                        //释放新的header节点的prev引用                        header.prev = null;                 }                 else                 {
                           //获取删除点的前一个节点                        Node prev = getNodeByIndex(index - 1);                        //获取将要被删除的节点                        del = prev.next;                        //让被删除节点的next指向被删除节点的下一个节点                        prev.next = del.next;                        //让被删除节点的下一个节点的prev指向prev节点                        if (del.next != null)                        {
                                  del.next.prev = prev;                        }                                    //将被删除节点的prev、next引用赋为null                        del.prev = null;                        del.next = null;                 }                 size--;                 return del.data;           }           //删除链式线性表中最后一个元素         public T remove()           {
                    return delete(size - 1);           }           //判断链式线性表是否为空链表           public boolean empty()           {
                    return size == 0;           }           //清空线性表           public void clear()           {
                    //将底层数组所有元素赋为null                 header = null;                 tail = null;                 size = 0;           }           public String toString()                     {
                    //链表为空链表时                 if (empty())                 {
                          return "[]";                 }                 else                 {
                          StringBuilder sb = new StringBuilder("[");                       for (Node current = header ; current != null                             ; current = current.next )                       {
                                sb.append(current.data.toString() + ", ");                       }                       int len = sb.length();                       return sb.delete(len - 2 , len).append("]").toString();                 }           }           public String reverseToString()           {
                    //链表为空链表时                 if (empty())                 {
                          return "[]";                 }                 else                 {
                          StringBuilder sb = new StringBuilder("[");                       for (Node current = tail ; current != null                              ; current = current.prev )                       {
                                sb.append(current.data.toString() + ", ");                       }                       int len = sb.length();                       return sb.delete(len - 2 , len).append("]").toString();                 }           }     }
   

由于双向链表需要同时维护两个方向的指针，因此添加节点、删除节点时的指针维护成本更大；但双向链表具有两个方向的指针，因此可以向两个方向搜索节点，因此双向链表在搜索节点、删除指定索引处节点时具有较好的性能。

2.3 循环链表

循环链表是一种首尾相接的链表。将单链表的尾节点next指针改为引用单链表header节点，这个单链表就成了循环链表。

循环链表具有一个显著特征：从链表的任一节点出发均可找到表中其他所有节点，因此循环链表可以被视为“无头无尾”，

2.4 线性功能

线性表本质上是一个充当容器的工具类，当程序有一组结构相同的数据元素需要保存时，就可以考虑使用线性表来保存它们。

从某种程度来看，线性表是数组的加强，线性表比数组多了如下几个功能。

• 线性表的长度可以动态改变，但Java数组的长度是固定的；
• 线性表可以插入元素，数组无法插入元素；
• 线性表可以删除元素，数组无法删除元素，数组只能将指定元素赋为null，但各种元素依然存在；
• 线性表提供方法来搜索指定元素的位置，但数组一般不提供该方法；
• 线性表提供方法来清空所有元素，但数组一般不提供类似方法。

从上面线性表的实现能发现线性表比数组功能强大的理由：顺序结构的线性表可以说是包装过的数组，自然会提供更多额外的方法来简化操作。

对于大部分Java程序员来说，其实经常在使用线性表List。Java的List接口就代表了线性表，线性表的两种实现分别是ArrayList和LinkedList，其中LinkedList还是一个双向链表。

转载地址：https://blog.csdn.net/ynchyong/article/details/112316728 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！