Javaのベクトルとリストの違いは何ですか?

vector と list の違い

● Vector はランダムアクセス効率が高いですが、挿入や削除の際に移動する必要があります（ただし、尾) データの操作は困難です。

##●リスト アクセスではリンク リスト全体を走査する必要があり、ランダム アクセスの効率は低くなります。ただし、ポインターの位置を変更するだけでデータの挿入と削除を行う方が便利です。

##●リストは一方向、ベクトルは双方向です。

#●vector 内の反復子は使用後無効になりますが、list 内の反復子は使用後も引き続き使用できます。

ベクトルの使用

連続ストレージ構造: ベクトルは、動的な拡張を実現し、配列への効率的なアクセスと、配列の最後での削除と挿入をサポートするオブジェクト配列です。配列の途中や先頭の削除や挿入などの操作は比較的難しく、大量のデータを移動する必要があります。配列との最大の違いは、ベクトルではプログラマ自身が容量の問題を考慮する必要がなく、ライブラリ自体が動的に容量の拡張を実現しているのに対し、配列ではプログラマが拡張のための拡張関数を手動で記述する必要があることです。

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; //可用内存空间的末尾节点
};

リストの使用

非連続ストレージ構造: リストは双方向をサポートする二重リンクリスト構造です。リンクされたリストの走査。各ノードには、要素自体、前の要素を指すノード (prev)、次の要素を指すノード (next) の 3 つの情報が含まれます。したがって、リストは任意の場所のデータ要素に効率的にアクセス、挿入、削除できます。追加のポインターのメンテナンスが含まれるため、オーバーヘッドが比較的高くなります。

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;
};

推奨学習:

Java ビデオ チュートリアル

以上がJavaのベクトルとリストの違いは何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。