리스트와 배열

리스트 ( List ) : 일련의 동일한 타입의 항목들을 의미

배열 ( Array ) : 

동일한 타입의 원소들이 연속적인 메모리 공간에 할당되어 각 항목이 하나의 원소에 저장되는 기본적인 자료구조

특정 원소에 접근할 때에는 배열의 인덱스를 이용하여 O(1)시간에 접근할 수 있다.

그러나 새 항목이 배열 중간에 삽입되거나 , 중간에 있는 항목을 삭제한다면

뒤 따르는 항목들을 한 칸씩 뒤로 or 앞으로 이동시켜야 하기 때문에 

삽입 or 삭제 연산은 항상 O(1)시간에 수행할 수 없다.

프로그램이 실행되는 동안에 할당된 메모리 공간을 확장 or 축소하는 배열을 동적배열.

단순연결리스트(Singly Linked List) : 동적 메모리 할당을 이용해 리스트를 구현하는 가장 간단한 형태의 자료구조

즉 , 동적 메모리 할당을 받아 노드(Node)를 저장하고 , 노드는 레퍼런스를 이용하여 다음 노드를 가리키도록 만들어 

노드들을 한 줄로 연결시킨다.

1차원 배열에서는 새 항목을 삽입 or  삭제하는 경우 , 뒤 따르는 항목들이 한 칸씩 뒤나 앞으로 이동해야 하는 경우가 발생한다.

그러나 연결리스트에서는 삽입 or 삭제 시 항목들의 이동이 필요 없다.

또한 배열의 경우 일반적으로 최초에 배열의 크기를 예측하여 결정해야 하므로 배열에 빈 공간을 가지고 있으나,

연결리스트는 빈 공간이 존재하지 않는다.

연결리스트에서는 항목을 탐색하려면 항상 첫 노드부터 원하는 노드를 찾을 때까지 차례로 방문하는 순차탐색을 해야만 한다.

배열은 각 원소에 레퍼런스를 저장할 필요가 없지만 , 연결리스트는 각 노드마다 레퍼런스를 저장할 공간이 필요하다 .

	public class Node<E> {
		private E item;
		private Node<E> next;
		public Node(E newItem, Node<E> node) {
			item = newItem;
			next = node;
		}
		// get , set
		public E getItem() {
			return item;
		}
		public Node<E> getNext()
		{
			return next;
		}
		public void setItem(E newItem) 
		{
			item = newItem;
		}
		public void setNext(Node<E> newNext) 
		{
			next = newNext;
		}
	}


 // Node객체는 항목을 저장할 item과 Node레퍼런스를 저장하는 next를 가진다.
 // Line 05 ~ 08 은 Node 생성자이다 . 

삽입 연산 : 새 항목을 연결리스트의 맨 앞에 다음에 삽입하는 경우 or

새 항목이 p가 가리키는 노드 다음에 삽입하는 두 가지의 메소드로 구현된다.

public void insertFront(E newItem)
{
	head = new Node(newItem, head);
	size++;
}

insertAfter()메소드는 p가 가리키는 노드의 다음에 새 노드를 삽입한다.

public void insertAfter(E newItem, Node p)
{
	p.setNext(new Node(newItem, p.getNext()));
	size ++;
}

삭제 연산은 연결리스트의 첫 노드를 삭제하는 경우와 

p가 가리키는 노드의 다음 노드를 삭제하는 두 가지 메소드로 구현한다.

deleteFront() 메소드는 리스트가 empty가 아닐 때 , 리스트의 첫 노드를 삭제한다.

public void deleteFront()
{
	if(isEmpty()) throw new NoSuchElementException();
	head = head.getNext();
	size--;
}

deleteAfter() 메소드는 p가 가리키는 노드의 다음 노드를 삭제한다.

public void deleteAfter(Node p)
{
	if(p == null) throw new NoSuchElementException();
	Node t = p.getNext();
	p.setNext(t.getNext());
	t.setNext(null);
	size--;
}

이중연결리스트 ( Doubly Linked List ) : 각 노드가 두 개의 레퍼런스를 가지고 각각 이전 노드와 다음 노드를 가리키는 연결리스트

각 노드마다 추가로 한 개의 레퍼런스를 추가로 저장해야 한다는 단점을 가진다 .