리스트

리스트 (List)

선형 자료구조로 순서를 가지고 일렬로 나열한 원소들의 모임으로 정의한다. 순서가 있다는 점에서 집합과는 구별이 된다.

배열과 비슷한 구조를 띄고 있지만, 배열의 단점 즉 크기가 고정적이라는 점을 보완한다.

• 시간복잡도
  • 조회 : O(n)
  • 삽입, 삭제 (가장 앞, 뒤) : O(1)

List 컬렉션 클래스

List 인터페이스를 구현한 모든 List 컬렉션 클래스는 다음 특징을 가진다.

1. 요소의 저장 순서가 유지된다.
2. 같은 요소의 중복 저장을 허용한다.
   • ArrayList<E>
   • LinkedList<E>
   • Vector<E>
   • Stack<E>

ArrayList 클래스

JDK 1.2 부터 제공된 ArrayList 클래스는 내부적으로 배열을 이용하여 요소를 저장한다.

배열을 이용하기 때문에,

• 인덱스를 이용해 배열 요소에 빠르게 접근 가능
• 크기를 늘리기 위해서는 새로운 배열 생성 및 기존 요소를 옮기는 복잡한 과정 수행 (배열은 크기 변경x)
  • 이 과정은 자동으로 수행되지만, 요소의 추가 및 삭제 작업에 걸리는 시간이 매우 길어진다.
• ArrayList 생성

ArrayList<String> arrList = new ArrayList<String>();

• 요소 추가

arrList.add("element");
arrList.add("element");  // 중복 허용

• 요소 제거

arrList.remove(1);

• 요소 출력

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

for (String s : arrayList) {
    System.out.println(s + " ");
}

Iterator<String> iterator = arrayList.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next() + " ");
}

• Collections 클래스를 이용한 요소 정렬

Collections.sort(arrList);

• 요소 변경

arrList.set(0, "change");

• 요소의 총 개수

arrList.size();

LinkedList 클래스

배열의 단점을 보완하기 위해서 나온 자료구조로 불연속적으로 존재하는 데이터를 서로 연결(Link)한 형태로 구성되어 있다.

• 배열의 단점
  • 크기를 변경할 수 없다.
    • 크기를 변경할 수 없기 때문에 새로운 배열을 생성해서 데이터를 복사하는 작업이 필요
    • 실행속도를 향상시키기 위해서는 큰 크기의 배열을 생성해야 하므로 메모리가 낭비된다.
  • 비순차적인 데이터 추가 및 삭제에 시간이 많이 걸린다.
    • 차례대로 데이터를 추가하고 마지막 데이터를 삭제하는 과정은 빠름
    • 단, 배열의 중간에 데이터를 추가하려면 빈 자리를 만들기 위해 다른 데이터를 복사해서 이동해야 하기에 시간이 많이 걸린다.

LinkedList는 중간에 데이터를 추가 또는 삭제하더라도 전체의 인덱스가 한 칸씩 뒤로 밀리거나 당겨지는 일이 없기에 추가나 삭제가 용이하나, 인덱스가 없기에 특정 요소에 접근하기 위해서는 순차 탐색이 필요하여 탐색 속도가 떨어진다.

단일 연결 리스트

• 구조

요소를 추가하고 싶은 경우 새로운 요소를 생성한 다음 추가하고자 하는 위치의 이전 요소의 참조를 새로운 요소의 참조로 변경해주고, 새로운 요소가 그 다음 요소를 참조하도록 변경해주면 끝이므로 처리속도가 매우 빠르다.

요소를 삭제하고 싶은 경우 삭제하고자 하는 요소의 이전요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 참조값만 변경하면 된다. 배열처럼 데이터를 이동하기 위해 복사하는 과정이 필요없기에 처리속도가 매우 빠르다.

• 생성

LinkedList list = new LinkedList();

LinkedList<Students> students = new LinkedList<Student>();

LinkedList<Integer> ages = new LinkedList<Integer>();

LinkedList<Integer> bookCount = new LinkedList<>();

LinkedList<Integer> coffeeCount = new LinkedList<Integer>(Arrays.asList(3,4));

• 요소 추가

LinkedList<Integer> ages = new LinkedList<Integer>();
ages.addFirst(10);   // 맨 앞에 데이터 추가
ages.addLast(50);    // 맨 뒤에 데이터 추가
ages.add(25);        // 중간에 데이터 추가
ages.add(1, 31);     // index 1 뒤에 데이터 추가

• 요소 삭제

LinkedList<Integer> ages = new LinkedList<Integer>();
ages.addFirst(10);   // 맨 앞에 데이터 추가
ages.addLast(50);    // 맨 뒤에 데이터 추가
ages.add(25);        // 중간에 데이터 추가
ages.add(1, 31);     // index 1 뒤에 데이터 추가

• 크기

LinkedList<Integer> ages = new LinkedList<Integer>();
System.out.prinltn(ages.size())

• 값 검색

LinkedList<Integer> ages = new LinkedList<Integer>();
System.out.println(ages.contains(25)) // ages에 25이 있는지 검색함. 결과값은 boolean
System.out.println(ages.indexOf(25))  // 25이 있는 index 반환 없으면 -1

💡

컬렉션	읽기 (접근시간)	추가/삭제	비고
ArrayList	빠르다	느리다	순간적인 추가 삭제는 빠름, 비효율적인 메모리 사용
LinkedList	느리다	빠르다	데이터가 많을수록 접근성이 떨어짐

Vector 클래스

JDK1.0 부터 사용해 온 ArrayList 클래스와 같은 동작을 수행하는 클래스로 이 클래스에서 사용 할 수 있는 메소드는 ArrayList 클래스에서 사용할 수 있는 메소드와 거의 같다.

현재에는 기존 코드와의 호환성을 위해서만 남아있으므로, Vector 클래스보다는 ArrayList 클래스를 사용하는 것이 좋다.

Stack 클래스

자료구조 중 하나인 Stack의 사전적 정의는 ‘쌓다’, ‘더미’로, 상자에 물건을 쌓아 올리듯이 데이터를 쌓아 올리는 자료 구조라고 할 수 있다.

상자에 물건을 쌓아 올리면 꺼낼 때는 나중에 올린 상자를 먼저 꺼내듯이 나중에 들어간 것이 먼저 나오는 Last In First Out (LIFO) 형태이다.

https://coding-factory.tistory.com/601

• Stack 선언

import java.util.Stack

Stack<Integer> stack = new Stack();

• 값 추가

  

stack.push(1);

push 메소드를 활용하면 데이터가 위와같이 쌓이게 된다.

• 값 삭제

stack.pop();   // 상단 값 제거
stack.clear(); // stack 전체 값 제거 (초기화)

• 상단 값 출력

stack.peek();  // stack의 가장 상단의 값 출력

• 그 외
  • size() : 크기
  • empty() : 비어있는지 아닌지 (true/false)
  • contains() : 포함되어 있는지 아닌지 (true/false)

Array vs List

Array 장단점

데이터가 많아지고 그룹 관리의 필요에 따라 배열을 사용한다.

고정된 크기를 갖는 같은 자료형의 원소들이 연속적인(논리적 저장순서와 물리적 저장순서 일치) 형태로 구성된 자료 구조

• 장점
  • 인덱스를 통한 검색이 용이
  • 연속된 메모리 공간에 할당되어 순차 접근에도 빠르다.
  • 참조를 위한 추가 메모리 할당이 필요 없다.
• 단점
  • 크기가 고정되어 있기에 어떤 요소가 삭제되면 삭제된 상태를 빈 공간으로 남겨두어야 하기에 메모리가 낭비된다.
  • 정적이므로 배열의 크기를 컴파일 이전에 정해주어야 하며 컴파일 이후 배열의 크기를 변동 할 수 없다. (메모리 재사용 불가)

List 장단점

배열의 문제점을 해결하기 위한 자료구조로 빈틈없는 데이터의 적재라는 장점과 동적 크기 가질 수 있는 장점을 가진다.

순서가 있는 데이터의 모임

• 장점
  • 포인터를 통하여 다음 데이터의 위치를 가르키고 있어 삽입 삭제가 용이
  • 크기가 고정적이지 않음.
  • 메모리의 재사용 가능
• 단점
  • 구현이 상대적으로 복잡
  • 검색이 비효율적
  • 참조를 위한 메모리가 필요

💡 저장할 데이터의 개수가 정해져있고, 삽입 / 삭제 작업이 적고, 특정 위치의 데이터를 조회하는 작업이 많다 → 배열

💡 저장할 데이터의 개수가 미정이고, 삽입, 삭제 작업이 많고, 특정 위치 데이터를 조회하는 경우가 별로 없다면 → 리스트