리스트

단순 연결 리스트와 이중 연결 리스트로 나누어 정리할 예정이다.
단순 연결 리스트는 노드간 링크 포인터가 1개
이중 연결 리스트는 노드간 링크 포인터가 2개

연결 리스트

특성

자료의 논리적인 순서와 메모리 상의 물리적인 순서가 일치하지 않고, 개별적으로 위차하고 있는 각 원소를 연결하여 하나의 전체적인 자료구조를 이룸.

자료구조의 크기를 동적으로 조정할 수 있어, 메모리의 효율적인 사용이 가능

노드

연결 리스트에서 하나의 원소를 표현하는 building block
데이터 필드와 링크 필드로 구성되어 있다.

헤드

연결 리스트의 첫 노드에 대한 참조값을 갖고 있음

단순 연결

위 헤드에 대한 설명과 같은 구조를 갖는다.
단, 마지막에 링크 노드가 null이면 그 단순 연결 리스트의 마지막을 뜻 한다.

• 삽입

  • 첫 번째 삽입
    1. head가 가리키는 참조 값을 새로 넣을 노드의 link에 넣는다.
    2. 새로 넣을 노드의 주소를 head에 넣는다.

  • 마지막에 삽입
    1. head부터 기존 연결 리스트의 마지막 요소를 찾기
    2. 마지막 요소의 link에 새로 넣을 Node의 주소 넣기

  • 중간에 삽입
    1. head부터 넣을 위치를 가리키는 노드를 찾기
    2. 새로 넣을 Node의 link를 넣을 위치에 있는 Node를 가리킴
    3. 새로 넣을 Node의 주소 값을 n-1번째 노드의 링크에 삽입

• 삭제
  1. 삭제하려는 노드를 가리키는 Node의 link를 삭제 하려는 노드가 가리키는 link로 복사
  2. 삭제하려는 노드의 link 필드를 null로 해서 끊어주기
  3. 만약 선행 노드가 없다면, head가 바로 다음 노드를 가리키게 함
  

코드

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

	private Node<E> top;
	@Override
	public void push(E e) {
		// TODO Auto-generated method stub
		top = new Node<>(e, top);
	}

	@Override
	public E pop() {
		// TODO Auto-generated method stub
		if(isEmpty()) throw new EmptyStackException();
		Node<E> node = top;
		top = node.link;
		node.link = null;
		
		return node.data;
	}

	@Override
	public E peek() {
		// TODO Auto-generated method stub
		if(isEmpty()) throw new EmptyStackException();
		
		return top.data;
	}

	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return top == null;
	}

	@Override
	public int size() { // 연결 리스트를 전체 탐색하는 버전
		// TODO Auto-generated method stub
		int size = 0;
		for(Node<E> temp = top; temp != null; temp = temp.link) {
			size++;
		}
		return size;
	}
	
}