List

List

: data elements가 순차적이고, 중복을 허용하며 길이가 가변적인(dynamic allocation) 자료구조

• java.util 패키지의 하위 inteface로, Collection inteface와 Iterable inteface를 구현
• 대표적인 class로는 ArrayList와 LinkedList, Stack, Vector 등이 있음
• 대표적인 method

  method name	return type	contents
  add(E e)	boolean	요소 e 추가
  remove(Object o)	boolean	o와 같은 첫 번째 객체 삭제
  contains(Object o)	boolean	o가 컬렉션에 있는지 확인
  size()	int	현재 컬렉션에 있는 요소 개수 반환
  get(int index)	E	index에 저장된 원소 반환
  set(int index, E elements)	E	index 위치에 있는 요소를 elements로 바꿈
  isEmpty()	boolean	현재 컬렉션에 요소 존재 여부 확인
  equals(Object o)	boolean	o와 같은지 비교
  indexOf(Object o)	int	o가 있는 첫번째 요소의 위치 반환 (없을 경우 -1 반환)
  clear()	void	모든 요소들 제거

---

1. 링크드 리스트(Linked List)

: node와 node를 엮어 element 간의 연결(link)을 통해 구현한 list

• 구성요소
    - data: node의 값
    - next: 다음 노드를 가리키는 pointer 값

  class Node {
    Object data;
    Node next;
    Node (Object o) {
        this.data = o;
        this.next = null;
    }
  } 

• 첫번째 node는 head, 마지막 node는 tail으로 일컫음
  
  

2. 어레이리스트(Array List)

: 배열을 이용해 구현한 list

• 장점: 내부적으로 배열을 이용해 index로 접근하기 때문에 접근 속도가 빠름
• 단점: data의 추가/삭제가 느림
  (처음이나 중간에 data를 추가하면 기존의 데이터들이 한칸씩 뒤로 밀려나야하기 때문에/ 빈자리를 채우기 위해 한칸씩 앞으로 떙겨야하기 때문에)
  
  

• 기능
  - add: data 추가
  - get: data 추출
  - remove: data 삭제
  - size: list size return
  - iteration: list를 반복
  - contatins: 존재여부 비교

  
  

3. 스택(Stack)

: LIFO(Last In First Out, 후입선출) 구조를 갖는 자료구조로써 데이터 추가와 삭제가 한쪽 끝에서만 이루어짐

• 구성요소
  - top: data가 마지막으로 위치한 꼭대기 값
  
  

• 주요 기능
  - push: 데이터를 스택에 추가
  - pop: 데이터를 스택에서 삭제
  - peek: top에 위치한 data 출력

  public void push(E element);
  public E pop();
  public E peek();

    * pop과 peek의 차이는 remove 여부! peek은 단순히 data 출력만 하지만, pop은 data를 remove까지 한다.

4. 큐(Queue)

: FIFO(First In First Out, 선입선출) 구조를 갖는 자료구조로써 데이터 추거와 삭제가 양쪽 끝에서 이루어짐

• 구성요소
  - head: 데이터 삭제(remove)가 일어나는 출구
  - tail: 데이터 삽입(add)이 일어나는 입구
  
  
• 주요 기능
  - add: 데이터 삽입
  - remove: 데이터 삭제

  public void add(E element);
  public E remove();

  
  

5. 벡터(Vector)

: ArrayList와 동일한 구조를 가지며 배열의 크기가 늘어나고 줄어듬에 따라 자동으로 크기가 조절됌

• 한 번에 하나의 Thread가 접근 가능하여 Thread Safe 함