[자료구조] 순서와 중복이 있는 List

1. List란?

---

순서가 있는 데이터 집합으로 데이터의 중복을 허용 하는 자료구조다. 리스트의 종류에는 ArrayList, LinkedList, Vector, Stack이 있다.

2. List의 종류

---

2-1. ArrayList

연속적인 데이터의 리스트이다.
List 인터페이스를 상속받은 클래스로 크기가 가변적으로 변하는 리스트이다.

• 자바에서 제공하는 기본 배열보다는 느릴 수 있지만 동적 배열이 구현되어 있다.

• 배열과 ArrayList

  • 배열: 크기가 고정. 인덱스를 이용해 빠르게 접근할 때용
  • ArrayList : 크기가 가변. 데이터의 삽입과 삭제가 자주 발생할 때 사용
  • 더 자세한 배열과 ArrayList
    

2-2. LinkedList

양방향 연결 리스트(Doubly Linked List)로 구성되어 있다.
공간이 이어져 있는게 아니라, 떨어져 있다.

• LinkedList는 순차적 접근 방식이다.

• LinkedList는 주소값만 변경해주면 되기 때문에, 삽입과 삭제가 빠르다.

• ArrayList와 LinkedList

  • 빠른 삽입/삭제가 필요하면 LinkedList
  • 빠른 검색/조회가 필요하면 ArrayList

• LinkedList 선언과 사용

import java.util.LinkedList;
import java.util.List;

public class Application3 {
    public static void main(String[] args) {
        List<String> linkedList = new LinkedList<>();

        linkedList.add("apple");
        linkedList.add("banana");
        linkedList.add("orange");
        linkedList.add("banana");

        for(int i=0; i<linkedList.size(); i++){
            System.out.println(linkedList.get(i));
        }

        System.out.println(linkedList.isEmpty());
        linkedList.clear();
        System.out.println(linkedList.isEmpty());

    }
}

2-3. 그 외에 리스트들

• 이 외에도 리스트에는 vector, stack이 있다.

• vector는 ArrayList와 같다고 보면 된다 요즘에는 호환성 문제 때문에 그대로 남겨져 있는 것이므로, 잘 다루진 않는 부분이다. 그래서 따로 설명하지 않고 넘어갈 것이다.

• stack은 LIFO(Last In First Out)구조의 자료구조로 마지막에 들어간 값이 처음에 나오는 자료 구조이다.

• stack에 관한 설명은 queue와 함께 블로그에 따로 정리한 부분이 있기 때문에, 밑에 링크를 참고하면 된다.

  • Stack/Queue더 자세히 보기