리스트(List)

리스트(List)

 

리스트란?

• 데이터를 순차적으로 저장하는 선형 자료구조
• 순서를 가진 항목들의 모임
• 배열이 가지고 있는 인덱스라는 장점을 버리고 빈틈없는 데이터 적재라는 새로운 장점을 취한 자료구조
• 중복된 데이터의 저장을 허용
• ArrayList, LinkedList 등 여러 인터페이스를 구현한 자료형
• 자바스크립트, 파이썬 같은 경우 리스트를 따로 구현하지 않고 배열에 List의 기능 중 일부를 제공

 

1. ArrayList

• 배열을 이용해서 리스트를 구현하는 것을 의미하는 자료구조이다.

장점

• index를 통한 검색이 용이하다.
• 연속적이므로 메모리 관리가 편하다.
• 내부적으로 배열을 이용하기 때문에 인덱스를 이용하여 접근하는 것이 빠르다.

단점

• 데이터의 추가, 삭제가 느리다.
• 정적이므로 배열의 크기를 컴파일 이전에 정해주어야 한다. -> 컴파일 이후에 변경할 수 없다.
• 크기가 고정되어 있기 때문에 엘리먼트가 삭제되면, 삭제된 상태를 빈 공간으로 남겨두어야 한다. -> 메모리 낭비

즉, 검색이 잦은 경우 ArrayList를 사용하는 것이 좋다.

생성

import java.util.ArrayList;

ArrayList<> list = new ArrayList<>();

추가

• 제네릭 타입을 선언한다면 해당 타입만 추가 가능
• 기본적으로 리스트의 맨 뒤에 데이터 추가
• 특정 인덱스를 선택해 해당 위치에 데이터 추가 기능
• 데이터를 추가하는 과정에서 내부적으로 사용하는 배열이 꽉 차면 기존 배열 대비 2배 큰 새로운 배열을 만들고 기존의 데이터를 새로운 배열로 복제
• 사용자는 ArrayList의 크기에 신경 쓰지 않고 편하게 프로그램을 만들 수 있다.

list.add(1234);                 // list라는 ArrayList 맨 뒤에 1234 라는 int 타입 데이터를 추가
list.add("hello, World");    // list라는 ArrayList 맨 뒤에 "hello, World" 라는 String 타입 데이터를 추가
list.add(1, 50);            // 1이라는 인덱스에 50이라는 값을 추가

삭제

list.remove(2);        // list의 3번째 데이터를 삭제 (항상 배열, 리스트의 인덱스는 0부터 시작)

가져오기

list.get(20);        // 인덱스가 20인 데이터를 가져온다.

반복

• 자바에서는 ArrayList를 탐색하기 위한 방법으로 Iterator를 제공
• 객체지향 프로그래밍에서 사용하는 방법
• 먼저 Iterator 객체를 생성한다.

Iterator it = list.iterator();       // Iterator 객체는 list객체의 Iterator() 메소드를 통해 생성

while(it.hasNext()) {              // 다음 엘리먼트가 존재하면 while문 반복
    System.out.println(it.next());

    if(it.next() = 1234) {        // 다음 엘리먼트가 1234 라면
        it.remove();        // 해당 엘리먼트 삭제
    }
};

SMALL

ArrayList의 삽입, 삭제 과정

 

2. LinkedList

• 연결 리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료구조이다.
• 순서가 있는 엘리먼트의 모임으로 배열과는 다르게 빈 엘리먼트는 절대 허용하지 않는다.
• 배열이 가지고 있는 인덱스라는 장점을 버리고 대신 빈틈없는 데이터의 적재라는 장점을 취한다.
• 리스트에서 인덱스는 몇 번째 데이터인가 정도의 의미를 가진다. -> 순서

장점

• 데이터의 추가, 삭제 시 주소만 서로 연결시켜 주면 되기 때문에 데이터의 추가, 삭제가 ArrayList보다 빠르고 용이하다.
• 메모리의 재사용이 편리하다.
• 불연속적이므로 메모리 관리가 용이하다.
• 동적이므로 크기가 정해져 있지 않다.

단점

• 순차 접근만 가능하다. 그래서 접근 속도가 느리다.
• 중간 노드가 끊어지면 그다음 노드를 찾기가 힘들다.
• 단순 LinkedList는 단방향성을 갖고 있어 인덱스를 이용해 자료를 검색하는 애플리케이션에 적합하지 않다.
• 메모리 이곳저곳에 산재해 저장되어 있는 노드들을 접근하는데 ArrayList보다는 긴 지연 시간이 소모된다.
• 참조자를 위해 추가적인 메모리를 할당해야 한다.

즉, 삽입, 삭제가 잦은 경우 LinkedList를 사용하는 것이 좋다.

 

생성

import java.util.LinkedList;

LinkedList<> list = new LinkedList<>();

삽입

list.addFirst(data);    // 가장 앞에 데이터 추가
list.addLast(data);    // 가장 뒤에 데이터 추가
list.add(data):        // 가장 뒤에 데이터 추가
list.add(index, data);    // index 뒤에 데이터 추가
list.set(index, changedata);    // index의 데이터를 변경

삭제

list.removeFirst();    // 가장 앞의 데이터 제거
list.removeLast();    // 가장 뒤에 데이터 제거
list.remove();        // index 생략 시 0번째 index 제거
list.remove(index);    // index의 데이터 제거
list.clear();        // 리스트 안의 모든 데이터 제거

검색

list.contains(data);    // 리스트에 data가 있는지 검색, 있다면 true를 return
list.indexOf(data);    // 리스트에 data가 있는 index 반환, 없으면 -1을 return

출력

int a = 0;

a = list.get(index);    // index에 있는 data 출력
a = list.getFirst();    // 첫번째 데이터 출력
a = list.getLast();    // 마지막 데이터 출력
a = list.size();        // 리스트 사이즈 크기 출력

반응형

LinkedList의 삽입, 삭제 과정