자바에서 벡터와 리스트의 차이점

벡터 사용

연속 저장 구조: 벡터는 동적 성장을 달성할 수 있는 객체 배열로, 배열에 대한 효율적인 액세스와 배열 끝의 삭제 및 삽입 작업, 중간 및 머리 삽입은 상대적으로 어렵고 많은 양의 데이터를 이동해야 합니다. (추천 학습: java 과정)

벡터의 가장 큰 차이점은 벡터는 프로그래머가 용량 문제를 스스로 고려할 필요가 없다는 점입니다. 라이브러리 자체는 용량의 동적 증가를 실현했지만 배열은 프로그래머가 확장 기능을 수동으로 작성해야 합니다. 점진적인 확장.

벡터 시뮬레이션 구현

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)라는 세 가지 정보가 포함됩니다.

그래서 목록은 모든 위치에서 데이터 요소에 효율적으로 액세스, 삽입 및 삭제할 수 있습니다. 추가 포인터를 유지 관리해야 하기 때문에 오버헤드가 상대적으로 높습니다.

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

벡터와 리스트의 차이점

*벡터는 Random Access 효율성이 높지만 삽입과 삭제 시(tail 제외) 데이터를 이동해야 하므로 쉽지 않습니다. 작동하다.

*리스트 접근은 연결리스트 전체를 순회해야 하며, 랜덤 접근 효율성이 낮습니다. 하지만 데이터를 삽입하고 삭제하는 것이 더 편리합니다. 포인터의 포인팅을 변경하기만 하면 됩니다.

*목록은 단방향이고 벡터는 양방향입니다.

*벡터의 반복자는 사용 후 무효화되지만 목록의 반복자는 사용 후 계속 사용할 수 있습니다.

위 내용은 자바에서 벡터와 리스트의 차이점의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!