SeSAC 14일차 / 자료 구조(리스트)

SeSAC 14일차(2023-08-03)
자료 구조(리스트)

---

 

리스트(List)

 

컬렉션과 제네릭

• 컬렉션
  • 크기가 고정되지 않고 가변성을 확장시킨 자료구조의 모음
  • 요소의 개수에 따라 크기 자동 조절
  • 요소의 삽입, 삭제에 따른 요소의 위치 자동 이동
  • Collection<E> 인터페이스를 상속받는 객체들이 속함

 

 

 

• 제네릭
  • 컬렉션 타입 선언시 컬렉션 안에 들어가는 항목의 타입을 지정
  • 컬렉션의 요소는 객체만 가능
    • int, char, double 같은 기본 타입 사용 불가
    • Integer, Character, Double 등의 객체로 제네릭 선언 해야함.
  •  Collection<E>
    • <E>: 컬렉션의 항목 타입
  • Map<<K, V>
    • <K>: 키 항목 타입
    • <V>: 값 항목 타입

 

 

 

 

 

리스트(List)

• Linked List
  • 순서가 있는 자료구조
  • 항목의 데이터와 다음 항목의 위치를 같이 저장하여 다음 항목을 찾아간다.
    • 헤더: 다음 항목의 위치 저장
    • 데이터: 항목의 값 저장
  • 항목을 추가하기 용이
  • 항목에 접근하려면 헤더부터 시작하여 차례대로 접근
  • 헤더의 접근 시작 위치에 따라 stack 또는 queue 구조로 활용 가능
    • stack: 꼬리만 접근
    • queue, deque: 헤더와 꼬리 둘다 접근
  • 메모리 상에 항목 데이터들이 한 공간에 있지 않음

 

 

 

• Array List
  • ArrayList와 Vector의 구조는 배열로 이루어져 있다.
    • 크기 조정 가능한 배열
    • 데이터가 추가되면 배열 크기 확장
  • 인덱스의 접근이 많으면 ArrayList, 데이터의 추가와 헤더 접근이 많으면 LinkedList

 

 

 

• 리스트 생성
  • List 인터페이스를 상속받는 인터페이스 생성
  • 리스트는 개수를 지정하지 않아도 된다.

 

ex)

// 클래스 타입으로 인스턴스 생성

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

ArrayList<Integer> arrayList = new ArrayList<Integer>();

Vector<Integer> vector = new Vector<Integer>();

 

// 인터페이스 타입으로 업캐스팅 인스턴스 생성

List<Integer> list1 = new LinkedList<Integer>();

List<Integer> list2 = new ArrayList<Integer>();

List<Integer> list3 = new Vector<Integer>();

 

 

 

• 리스트의 메소드
  • add(값): 마지막 인덱스 다음에 값 추가
  • add(인덱스, 값): 해당 인덱스에 값 추가
  • toString(): 리스트를 문자열로 치환
  • get(인덱스): 해당 인덱스의 값 반환
  • remove(인덱스): 해당 인덱스의 값 제거
  • size(): 항목 개수 반환
  • contains(값): 항목들 중 해당 값이 포함되면 true, 아니면 false
  • for-each 활용: for(int i: list) { sout(i + “ “); }

 

 

 

• 리스트 활용
  • 제네릭 타입 설정에 따라 원하는 타입을 저장하여 활용

 

ex)

// 클래스 타입으로 인스턴스 생성

List<Mydata> list = new ArrayList<Mydata>():

 

list.add(new Mydata(1, “자바”));

list.add(new Mydata(2, “기초”));

 

// 전체 항목 출력

for (Mydata md: list) {

sout(md.getName());

}

 

// 1번 항목 출력

Mydata md = list.get(1);

sout(md.getName());

 

 

 

 

 

스택과 큐

 

스택(Stack)

• Stack
  • LIFO 후입선출 방식으로 데이터를 저장하고 접근
  • Stack 클래스나 Deque 인터페이스의 하위 클래스로 구성(LinkedLIst)
  • 재귀 방식의 알고리즘을 구현하는데 사용

 

 

• Stack
  • push() 구조의 맨 뒤에 항목 추가
  • pop() 맨 뒤 항목을 구조에서 제거하고 반환
  • Vector 클래스를 상속하여 배열의 구조로 스택 활용

 

 

• Deque
  • Queue 인터페이스의 확장이지만 양방향 접근이 가능하여 스택으로도 활용
  • addFirst(), removeFirst() 맨 앞에 항목 추가, 제거 반환
  • addLast(), removeLast() 맨 끝에 항목 추가, 제거 반환

 

 

 

• Stack 생성 및 push
  • Stack 타입 변수 정의 및 Stack 인스턴스 생성
  • push()를 통해 맨 끝에 데이터 추가

 

ex)

// MyData 제네릭으로 Stack 인스턴스 생성

Stack<Mydata> stack = new Stack<MyData>();

 

stack.push(new MyData((0, “자바”));

stack.push(new MyData((1, “기초”));

 

for (MyData md: stack) sout(md.getName() + “”);

⇒ 자바 기초 출력

 

 

 

• Stack pop과 peek
  • pop()를 통해 맨 끝의 데이터 제거 후 반환
  • peek()를 통해 맨 끝의 데이터 반환

 

ex)

// 스택에서 마지막 항목 제거 후 반환

MyData md1 = stack.pop();

sout(md1.getName());

 

// 스택에서 마지막 항목 반환만

MyData md2 = stack.peek();

sout(md2.getName());

 

 

 

 

 

큐(Queue)

• Queue
  • FIFO 선입선출 방식으로 데이터를 저장하고 접근
  • Queue 인터페이스 또는 Deque 인터페이스의 하위 클래스로 구성
  • 인덱스 접근이 불가능

 

 

• Queue
  • offer() 구조의 맨 끝에 항목 추가
  • poll() 맨 앞 항목을 구조에서 제거하고 반환

 

 

• Deque
  • offerLast() 구조의 맨 끝에 항목 추가
  • pollFirst() 맨 앞 항목을 구조에서 제거하고 반환

 

 

 

• Queue 생성 및 offer
  • offer()를 통해 맨 끝에 데이터 추가
  • Queue 타입으로 하위 인스턴스를 업캐스팅

 

ex)

// LinkedList를 Queue 타입으로 업캐스팅

Queue<MyData> queue = new LinkedList<MyData>();

 

queue.offer(new MyData(0, “자바”));

queue.offer(new MyData(1, “기초”));

 

for(MyData md: queue) sout(md.getName() + “ “);

⇒ 자바 기초

 

 

 

• Queue poll과 peek
  • poll()를 통해 맨 앞의 데이터 제거 후 반환
  • peek()를 통해 맨 앞의 데이터 반환

ex)

// 큐에서 첫번째 항목 제거 후 반환

MyData md1 = queue.poll();

sout(md1.getName());

 

// 큐에서 첫번째 항목 반환만

MyData md2 = queue.peek();

sout(md2.getName());

 

 

 

 

 

데크(Deque)

• Deque
  • 양방향 접근이 가능한 Queue의 확장 인터페이스
  • FIFO, LIFO 둘 다 가능하며 원하는 입출 방식을 정할 수 있다.
  • 인덱스 접근 불가

 

 

 

• Queue 생성 및 offer
  • Queue 타입으로 하위 인스턴스를 업캐스팅
  • offerLast(), offerFirst(), addLast(), addFirst() 활용하여 데이터 추가

 

ex)

Deque<MyData> dq = new LinkedList<MyData>();

 

// 맨 끝 추가

dq.offerLast(new MyData(1, “자바”));

dq.addLast(new MyData(2, “자료구조”));

 

// 맨 앞 추가

dq.offerFirst(new MyData(0, “기초”));

 

 

 

• Queue poll과 peek
  • pollFirst(), pollLast(), removeFirst(), removeLast() 활용하여 제거 반환
  • peekfirst(), peekLast() 활용하여 반환

 

ex)

// 첫번째 항목 제거 반환

MyData md1 = dq.pollFirst();

sout(md1.getName());

 

// 마지막 항목 반환

MyData md2 = dq.peekLast();

sout(md2.getName());

 

// 마지막 항목 제거 반환

MyData md3 = dq.removeLast();

sout(”md3.getName());

 

 

 

 

 

오늘의 실습 코드

https://github.com/yubin-im/SeSAC/tree/600b0977194b49882400687fe0ea2af2219053ad/20230803