[자료구조] 02. 연결리스트

단순 연결 리스트는 동적 메모리를 이용해 리스트를 구현하는 가장 간단한 형태의 자료구조 입니다.

동적으로 할당을 받아 노드를 저장하고, 노드 내부적으로 다음 노드를 가리키는 레퍼런스를 이용해 노드들을 잇습니다.

앞서 확인한 배열리스트에서는 삽입 또는 삭제의 경우 뒤의 모든 원소들을 옮겨줘야 했습니다.

하지만 연결리스트에서는 레퍼런스만 조정해주면 되기 때문에, 원소들의 이동이 필요 없습니다.

또한 원소를 삽입할때마다 공간을 할당받아 넣기 때문에, 최초에 공간을 생성하는 등의 초기화가 필요하지 않습니다.

 

하지만 검색의 경우, 연결리스트는 앞의 레퍼런스부터 따라 들어가야 한다는 단점이 있습니다.

배열의 경우 인덱스를 통해 직접 접근이 가능하지만, 연결리스트는 순차탐색을 해야 합니다.

이런 단순연결리스트는 스택과 큐, 해싱 등에서 사용되기도 합니다.

 

단순연결리스트의 Node 를 정의한 노드 클래스입니다.

// 연결리스트에서 사용할 노드 클래스
public class Node<E>
{
	// 원소를 저장할 item 과, 다음 노드를 가리키는 레퍼런스인 next
	private E item;
	private Node<E> next;
	
	public Node(E item, Node<E> next)
	{
		this.item = item;
		this.next = next;
	}
	
	// get / set 메써드
	public E getItem() { return item; }
	public Node<E> getNext() { return next; }
	public void setItem(E item) { this.item = item; }
	public void setNext(Node<E> next) { this.next = next; }
}

 

검색 연산입니다.

// 리스트 안에 특정 원소가 있는지 검색하고, 있다면 해당 위치 반환
public int search(E target)
{	
	// 리스트의 처음부터 순차탐색해야 하기 때문에, 헤드부터 시작
	Node p = head;
	// 리스트를 전부 순회하며 검색
	for(int i = 0 ; i < size ; i++)
	{
		// 현재 아이템이 찾는 원소와 같다면 위치를 반환하고
		if(p.getItem() == target) return i;
		// 아니라면 다음 원소를 검색
		p = p.getNext();
	}
	return -1;
}

// 리스트의 k 번째 원소를 반환 (추가 구현)
public E search(int k)
{
	// k 번째 원소까지 순차 접근한 뒤
	Node p = head;
	for(int i = 0 ; i < k ; i++) p = p.getNext();
	// 해당 값 반환
	return (E)p.getItem();
}

 

삽입 연산입니다.

// 리스트의 맨 앞부분에 원소 삽입
public void insertFront(E item)
{
	// 기존의 헤드를 다음으로 가리키는 새로운 노드를 만든 뒤, 그 노드를 새롭게 헤드로 지정 
	head = new Node(item, head);
	size++;
}

// 특정 노드의 다음 위치에 원소 삽입
public void insertAfter(E item, Node p)
{
	// 주어진 노드 p 의 뒷 원소를 가리키는 레퍼런스를 가진 노드를 만들고, 해당 노드를 p 가 가리킴
	p.setNext(new Node(item, p.getNext()));
	size++;
}

// 주어진 위치 k 의 뒤에 원소 삽입 (추가 구현)
public void insertAfter(E item, int k)
{
	if(k >= size) throw new NoSuchElementException();
	Node p = head;
	for(int i = 0 ; i < k ; i++)
	{
		p = p.getNext();
	}
	insertAfter(item, p);
}

 

삭제 연산입니다.

// 리스트의 맨 앞 원소를 삭제
public void deleteFront()
{
	if(size == 0) throw new NoSuchElementException();
	// 현재 헤드노드가 가리키는 다음노드를 다시 헤드로 바꿔줌으로써, 기존 헤드는 가비지 콜렉터가 수거
	head = head.getNext();
	size--;
}

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

 

수행시간

단순연결리스트의 검색 연산은, 첫 노드부터 순차적으로 방문해야 하기 때문에 O(N) 입니다.

그러나 삽입이나 삭제는 상수 개의 레퍼런스만 변경하기 때문에 O(1) 입니다.