[알고리즘] [9] 연결리스트

1. 리스트 (List)

• 순서를 가지는 데이터의 집합으로 추상 자료형이다.
• 데이터의 중복이 허용된다.
• 구현 방법에 따라 크게 순차 리스트, 연결 리스트로 나뉜다.

---

2. 순차 리스트 : 배열을 기반으로 구현되는 리스트

• 1차원 배열에 순서대로 저장한다.
• 배열의 인덱스로 데이터에 접근한다.
• 특정 위치에 원소를 삽입 후 삽입 위치 다음의 항목을 뒤로 이동한다.
• 특정 위치의 원소를 삭제 후 뒤의 원소들을 앞으로 이동시킨다.
• 단순 배열을 이용한 순차 리스트는 자료의 삽입 및 삭제에 소요되는 시간이 크다.

---

3. 연결 리스트 : 메모리의 동적 할당을 기반으로 구현되는 리스트

• 자료의 논리적 순서와 메모리 상의 물리적 순서가 일치하지 않는다.
• 개별적으로 위치하는 각 원소를 연결하여 전체 자료 구조를 구성한다.
• 원소의 물리적인 순서를 맞추는 작업을 필요로 하지 않으며, 자료구조의 크기를 동적으로 조정할 수 있다.
• 메모리의 효율적인 사용이 가능하다.

연결 리스트의 구조

• 노드 : 연결 리스트에서 원소를 표현하는 building block
  >> 데이터 필드 (Data) : 원소의 값을 저장한다.
  >> 링크 필드 (Link) : 다음 노드의 참조값을 저장한다.
  
  
• 헤드 : 연결 리스트의 첫 노드에 대한 참조값을 가진다.

연결 리스트의 종류

• 단순 연결 리스트
• 이중 연결 리스트
• 원형 연결 리스트

---

4. 연결 리스트를 활용한 스택 구현

// 각각의 노드는 자신의 data와 자신과 연결된 link로 구성된다.
// 단순 연결 리스트
public class Node<T> {

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

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

	@Override
	public String toString() {
		return "Node [data=" + data + ", link=" + link + "]";
	}
}

import java.util.EmptyStackException;

public class StackLinkedList<E> implements IStack<E> {

	private Node<E> top;
	
	@Override
    // 들어온 e의 data와 기존 top의 link를 top에 삽입한다.
	public void push(E e) {
		top = new Node<E>(e, top);
	}

	@Override
	public E pop() {
		if (isEmpty()) throw new EmptyStackException();
		Node<E> popNode = top;
		top = popNode.link;
		popNode.link = null;
		
		return popNode.data;
	}

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

	@Override
	public int size() {
		int cnt = 0;
		// size 계산 시 다음과 같이 반복문 작성이 가능하다.
		for (Node<E> temp = top; temp != null; temp = temp.link) ++cnt;
		return cnt;
	}

	@Override
	public E peek() {
		if (isEmpty()) throw new EmptyStackException();
		return top.data;
	}

}