Algorithm 6일차

알고리즘에서 리스트를 사용할 수 있다.

순서를 가진 데이터의 집합을 가리키는 추상자료형을 리스트라고 한다.
리스트는 동일한 데이터를 가질 수 있다.

리스트는 두 가지 종류가 있다.

1. 순차 리스트 : 배열을 기반으로 구현된 리스트
2. 연결 리스트 : 메모리의 동적할당을 기반으로 구현된 리스트

순차 리스트의 작동 원리는 아래와 같다.

1. 배열을 기반으로 만들어졌기 때문에 초기 배열 생성 시 배열의 크기를 설정해줘야한다.
   그리고 요소의 수가 배열의 크기보다 커지면 더 큰 배열을 재할당한다.
2. 인덱스로 배열의 요소에 접근 가능하다.
3. 요소를 삽입하면 해당 인덱스의 다음 요소를 한 칸씩 뒤로 이동해야 한다.
4. 요소를 삭제하면 해당 인덱스의 다음 요소를 한 칸씩 앞으로 이동해야 한다.

따라서, 요소의 갯수가 많고, 삽입 & 삭제 연산이 빈번하게 일어나면 소요 시간이 크게 증가한다.

연결 리스트의 구조는 헤드와 노드로 이뤄진다. 아래 설명을 살펴보자.

1. 헤드 : 연결 리스트의 첫 노드의 참조값을 가진다.
2. 노드 : 데이터 필드(원소의 값)와 링크 필드(다음 노드의 참조값)으로 이루진 블록이다.

연결 리스트는 노드를 연결하여 하나의 전체적인 자료구조를 이룬다.
연결 리스트의 종류는 단순 연결 리스트, 이중 연결 리스트, 원형 연결 리스트가 있다.

알고리즘에서 단순 연결 리스트를 활용할 수 있다.

단순 연결 리스트의 삽입 연산 원리는 아래와 같다.

1. 공백 리스트에 노드를 처음으로 삽입할 때
   1) 새로운 노드 new 생성
   
   2) new 데이터에 'A' 저장
   
   3) new 링크에 null 저장
   
   4) Head에 new 참조값 저장
   

2. 리스트 첫번째에 노드를 삽입할 때
   1) 새로운 노드 new 생성
   
   2) new 데이터에 'C' 저장
   
   3) new 링크에 Head에 저장된 참조값 저장
   
   4) Head에 new 참조값 저장
   

3. 리스트 마지막에 노드를 삽입할 때
   1) 새로운 노드 new 생성
   
   2) new 데이터에 'D' 저장, 링크에 null 저장
   
   3) 리스트 마지막 노드의 링크에 new 참조값 저장
   

4. 리스트의 두번째에 노드를 삽입할 때
   1) 새로운 노드 new의 데이터에 'B' 저장
   
   2) new의 링크에 삽입될 위치에 있는 노드 참조값 저장
   
   3) 삽입될 위치 바로 앞 노드의 링크에 new 참조값 저장
   

단순 연결 리스트의 삭제 연산 원리는 아래와 같다.

1. 리스트의 중간 노드를 삭제할 때
   1) 삭제한 노드 전 노드 찾기
   
   2) 삭제할 노드 전 링크에 삭제할 노드의 링크 저장
   
   3) 삭제한 노드의 링크에 null 저장
   

2. 리스트의 첫번째 노드를 삭제할 때
   1) 헤드에 삭제할 노드의 링크 저장
   
   2) 삭제할 노드의 링크에 null 저장
   

단순 연결 리스트를 스택으로 구현하면 아래와 같다.
1) 단순 연결 리스트가 구현할 인터페이스

package live06.dist;

public interface IStack<T> {
	void push(T e);
	T pop();
	T peek();
	boolean isEmpty();
	int size();
}

2) 단순 연결 리스트의 노드

package live06.dist;

public class Node<T> {
	T data;
	Node<T> link;
	
	public Node(T data, Node<T> link) {
		this.data = data;
		this.link = link;
	}
}

3) 단순 연결 리스트

package live06.dist;

public class LinkedListStack<T> implements IStack<T> {
	private Node<T> top;
	
	@Override
	public void push(T e) {
		top = new Node<T>(e, top);
	}

	@Override
	public T pop() {
		if (isEmpty()) {
			System.out.println("공백스택이어서 불가능합니다.");
			return null;
		}
		Node<T> popNode = top;
		top = popNode.link;
		popNode.link = null;
		
		return popNode.data;
	}

	@Override
	public T peek() {
		if (isEmpty()) {
			System.out.println("공백스택이어서 불가능합니다.");
			return null;
		}

		return top.data;
	}

	@Override
	public boolean isEmpty() {
		return top == null;
	}

	@Override
	public int size() {
		int res = 0;
		for (Node<T> temp = top; temp != null; temp = temp.link) {
			res++;
		}
		
		return res;
	}
}

4) 메인 함수

package live06.dist;

public class StackTest {

	public static void main(String[] args) {
		IStack<String> stack = new LinkedListStack<String>();
		
		System.out.println(stack.isEmpty());
		System.out.println(stack.size());
		System.out.println();
		
		stack.push("강수민");
		stack.push("전임송");
		stack.push("박정은");
		stack.push("송진현");
		
		System.out.println(stack.isEmpty());
		System.out.println(stack.peek());
		System.out.println(stack.size());
		System.out.println();
		
		System.out.println(stack.pop());
		System.out.println(stack.peek());
		System.out.println(stack.size());
	}
}

출력 결과는 아래와 같다.

true
0

false
송진현
4

송진현
박정은
3