2-1) 연결 리스트, 노드와 크기

 

아래 내용은 부스트코스 <자바로 구현하고 배우는 자료구조> 강의를 들으며 정리한 것입니다.

 

연결 리스트(Linked list)

포인터를 사용하여 여러 개의 노드를 연결하는 자료 구조로, 순차적인 데이터나 많은 양의 데이터를 정리하기 위해 사용한다.

 

배열과의 차이

배열의 경우 필요한 요소보다 지나치게 크거나 작게 만들어 조정해야 한다. (처음 선언한 배열의 크기 변경 불가능)
연결리스트는 항상 맞는 크기로 만들어지도록 설계된다. 또한 배열처럼 메모리에 연속적으로 나열되는 것이 아니라 데이터들이 연속적으로 나열되는 것이다.  + 삽입과 삭제가 용이하다. but 색인 시에는 시간이 걸린다.

Arrays 와 Linked lists의 정적 할당, 동적 할당 차이

출처: 

What’s a Linked List, Anyway? [Part 1]

 

연결리스트의 구조

노드(node)

1. next 포인터 공간
   인접한 노드를 가리키는 포인터
   다음 노드가 없을 경우 null을 가리킨다.
2. data 공간 (요소를 가리키는 일종의 포인터)
   노드에 넣는 데이터

 

Head

리스트의 첫 번째 노드를 가리키는 포인터. 연결 리스트에 접근할 수 있는 유일한 방법이다. (head.next, head.data)

Head에서 시작해 임시 포인터를 사용하여 각 노드를 순차적으로 탐색한다.

 

노드 정의하기

public class LinkedList<E> implemetns ListI<E>{
	class Node<E> {
    	E data;
        Node<E> next;
        public Node(E obj){
        	data = obj;
            next = null; 
		}
	} // 내부 클래스 노드: 외부 클래스의 객체, 메소드들만 접근 가능
    
	private Node<E> head;	
    Private int currentSize;	// 노드 개수를 세는 변수
    
    //생성자
    public LinkedList() {
    	head=null;
        currentSize=null;   
    }
}

제네릭의 매개변수형 타입<E>를 활용해 다음과 같이 구현하고, 연결리스트를 사용할 때 자료형을 지정한다.

next는 다른 노드를 가리키는 포인터이기 때문에 Node<E> 타입이다. 

 

 

노드의 개수 효율적으로 세기

currentSize 변수를 만들어 노드의 개수를 더 효율적으로 셀 수 있다.

노드의 개수를 하나씩 셀 경우, 매번 처음부터 세어야 하므로 요소가 n개면 n번 - 시간 복잡도는 O(n) 혹은 더 정확히 θ(n)이다.
currentSize라는 변수를 만들어놓고 리스트에 요소를 추가할 때마다 currentSize의 값을 늘리면, 리스트의 크기를 알고자 할 때 매번 처음부터 다시 셀 필요 없이 currentSize 변수를 통해 바로 알 수 있다. 시간 복잡도는 정확히 1(상수 시간)이 되기에 훨씬 효율적이다.

 

생각해보기

Q. 일상생활에서 연결 리스트처럼 여러 물건을 연결하여 정리하는 것에는 어떤 것이 있는가?

A. 네비게이션의 MapQuest - 단일 링크 리스트: 시작 위치부터 도착지점까지 각 단계를 순차적으로 수행 /

네이버 길찾기 등

Real-Life Example of a LinkedList

Real-Life Example of a Linked List

 

Q. next가 내부 클래스에 있지 않을 경우 어떤 문제가 발생할 것인가?
A. 외부에서 접근 가능해 값이 변경될 수 있고, 인접 노드의 위치를 찾을 수 없게 될 것이다.