Der Unterschied zwischen Vektor und Liste in Java

Verwendung von Vektor

Kontinuierliche Speicherstruktur: Vektor ist ein Objektarray, das dynamisches Wachstum erreichen kann und eine hohe Effizienz für Arrays unterstützt Zugriffs-, Lösch- und Einfügevorgänge am Ende des Arrays sowie Lösch- und Einfügungsvorgänge in der Mitte und am Kopf sind relativ schwierig und erfordern das Verschieben einer großen Datenmenge. (Empfohlenes Lernen: Java-Kurs)

Der größte Unterschied zwischen ihm und Arrays besteht darin, dass der Vektor nicht erfordert, dass Programmierer selbst Kapazitätsprobleme berücksichtigen. Die Bibliothek selbst hat ein dynamisches Kapazitätswachstum realisiert Arrays Programmierer müssen die Erweiterungsfunktion manuell schreiben, um die Erweiterung durchzuführen.

Simulationsimplementierung von Vector

template <class T>
class Vector
{
public:
  typedef T* Iterator;
  typedef const T* Iterator;
  Vector()
    :_start(NULL)
    ,_finish(NULL)
    ,_endOfStorage(NULL)
  {}
  void template<class T>
  PushBack(const T& x)
  {
    Iterator end = End();
    Insert(end, x);
  }
  void Insert(Iterator& pos, const T& x)
  {
    size_t n = pos - _start;
    if (_finish == _endOfStorage)
    {
      size_t len = Capacity() == 0 ? 3 :  Capacity()*2;
      Expand(len);
    }
    pos = _start+n;
    for (Iterator end = End(); end != pos; --end)
    {
      *end = *(end-1);
    }
    *pos = x;
    ++_finish;
  }
  Iterator End()
  {
    return _finish;
  }
  Iterator Begin()
  {
    return _start;
  }
  void Resize(size_t n, const T& val = T())//用Resize扩容时需要初始化空间，并且可以缩小容量
  {
    if (n < Size())
    {
      _finish = _start+n;
    }
    else
    {
      Reserve(n);
      size_t len = n-Size();
      for (size_t i = 0; i < len; ++i)
      {
        PushBack(val);
      }
    }
  }
  void Reserve(size_t n)//不用初始化空间，直接增容
  {
    Expand(n);
  }
  inline size_t Size()
  {
    return _finish-_start;
  }
  inline size_t Capacity()
  {
    return _endOfStorage-_start;
  }
  void Expand(size_t n)
  {
    const size_t size = Size();
    const size_t capacity = Capacity();
    if (n > capacity)
    {
      T* tmp = new T[n];
      for (size_t i = 0; i < size; ++i)
      {
        tmp[i] = _start[i];
      }
      delete[] _start;
      _start = tmp;
      _finish = _start+size;
      _endOfStorage = _start+n;
    }
  }
  T& operator[](size_t pos)
  {
    assert(pos < Size());
    return _start[pos];
  }
  const T& operator[](size_t pos) const
  {
    assert(pos < Size());
    return _start[pos];
  }
protected:
  Iterator _start; //指向第一个元素所在节点
  Iterator _finish; //指向最后一个元素所在节点的下一个节点
  Iterator _endOfStorage; //可用内存空间的末尾节点
};

Verwendung der Liste

Nicht kontinuierliche Speicherstruktur: Liste ist eine doppelt verknüpfte Liste Struktur, unterstützt die bidirektionale Durchquerung verknüpfter Listen. Jeder Knoten enthält drei Informationen: das Element selbst, den Knoten, der auf das vorherige Element zeigt (prev), und den Knoten, der auf das nächste Element zeigt (next).

Daher kann die Liste an jeder Position effizient auf Datenelemente zugreifen, diese einfügen und löschen. Da es sich um die Pflege zusätzlicher Zeiger handelt, ist der Overhead relativ hoch.

Simulierte Implementierung von List

template<class T>
class List
{
  typedef __ListNode<T> Node;
public:
  typedef __ListIterator<T, T&, T*> Iterator;
  typedef __ListIterator<T, const T&, const T*> ConstIterator;
  Iterator Begin()
  {
    return _head->_next;
  }
  Iterator End()
  {
    return _head;
  }
  ConstIterator Begin() const
  {
    return _head->_next;
  }
  ConstIterator End() const
  {
    return _head;
  }
  List()
  {
    _head = new Node(T());
    _head->_next = _head;
    _head->_prev = _head;
  }
  // l2(l1)
  List(const List& l)
  {
    _head = new Node(T());
    _head->_next = _head;
    _head->_prev = _head;
    ConstIterator it = l.Begin();
    while (it != l.End())
    {
      PushBack(*it);
      ++it;
    }
  }
  ~List()
  {
    Clear();
    delete _head;
    _head = NULL;
  }
  void Clear()
  {
    Iterator it = Begin();
    while (it != End())
    {
      Node* del = it._node;
      ++it;
      delete del;
    }
    _head->_next = _head;
    _head->_prev = _head;
  }
  void PushBack(const T& x)
  {
    Insert(End(), x);
  }
  void PushFront(const T& x)
  {
    Insert(Begin(), x);
  }
  void PopBack()
  {
    Erase(--End());
  }
  void PopFront()
  {
    Erase(Begin());
  }
  void Insert(Iterator pos, const T& x)
  {
    Node* cur = pos._node;
    Node* prev = cur->_prev;
    Node* tmp = new Node(x);
    prev->_next = tmp;
    tmp->_prev = prev;
    tmp->_next = cur;
    cur->_prev = prev;
  }
    Iterator Erase(Iterator& pos)
  {
    assert(pos != End());
    Node* prev = (pos._node)->_prev;
    Node* next = (pos._node)->_next;
    prev->_next = next;
    next->_prev = prev;
    delete pos._node;
    pos._node = prev;
        return Iterator(next);
  }
protected:
  Node* _head;
};

Der Unterschied zwischen Vektor und Liste

*Vector hat eine hohe Direktzugriffseffizienz, aber Beim Einfügen und Löschen (mit Ausnahme des Endes) müssen die Daten verschoben werden, was nicht einfach zu bedienen ist.

*Der Listenzugriff erfordert das Durchlaufen der gesamten verknüpften Liste und die Effizienz des Direktzugriffs ist gering. Es ist jedoch bequemer, Daten einzufügen und zu löschen, indem Sie einfach die Ausrichtung des Zeigers ändern.

*Liste ist unidirektional, Vektor ist bidirektional.

*Der Iterator im Vektor wird nach der Verwendung ungültig, während der Iterator in der Liste nach der Verwendung weiterhin verwendet werden kann.

Das obige ist der detaillierte Inhalt vonDer Unterschied zwischen Vektor und Liste in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!