[Java] 단일 링크드 리스트(Singly Linked-List) 간단하게 정의 및 구현 - 1

Linked-List (링크드 리스트)란?

링크드 리스트(linked list)는 데이터의 집합을 저장하는 자료구조 중 하나입니다. 여러 개의 노드(node)가 서로 연결(link)된 구조를 가지고 있으며, 각 노드는 데이터를 저장하는 부분과 다음 노드를 가리키는 포인터(pointer) 부분으로 이루어져 있습니다.

링크드 리스트는 배열과는 달리, 데이터의 위치가 메모리 상에서 연속적이지 않아도 됩니다. 따라서, 데이터의 추가, 삭제가 빈번하게 일어나는 상황에서는 배열보다 유용하게 사용될 수 있습니다.

링크드 리스트는 단방향 링크드 리스트(Singly Linked List)와 양방향 링크드 리스트(Doubly Linked List)로 나뉘어지는데, 이번 포스팅에서는 단방향 링크드 리스트에 대해서 구현해보겠습니다.

---

 

데이터 타입

기본 데이터 타입(primitive data types)인 경우, 변수는 실제 값을 직접 저장합니다. 

예를 들어, int, double, char 등이 기본 데이터 타입입니다. 따라서 다음과 같은 코드에서:

int a = 1;

변수 a는 값 1을 직접 저장하게 됩니다.

---

반면에 참조 데이터 타입(reference data types)인 경우, 변수는 실제 객체를 가리키는 포인터를 저장합니다.

예를 들어, 클래스 인스턴스와 배열이 참조 데이터 타입입니다:

String str = "hello";

위 코드에서 str 변수는 "Hello"라는 문자열 객체를 가리키는 포인터를 저장하게 됩니다.

---

 

Linked-List 구현

코드는 생각보다 엄청 간단한데, 다음과 같이 작성될 수 있습니다.

public class LinkedList{
    private int value;
    private LinkedList next;

    public static void main(String[] args){
        LinkedList list = new LinkedList();
        list.value = 5;
        list.next = null;
        
        list.next = new LinkedList();
        list.next.value = 2;

    }
}

위의 예제에서, LinkedList 클래스는 value와 next라는 두 개의 멤버 변수를 가지고 있습니다. 

value는 노드의 실제 값을 저장하고, next는 다음 노드를 참조하는 포인터입니다. 

 

main() 함수에서 list 객체를 생성하고, value 변수에 5를 할당하고, next 변수를 null로 설정합니다.

이로 인해 첫 번째 노드에 5가 저장되고 아무것도 가리키지 않는 객체가 만들어 집니다.

객체 이어 붙이기

자 그다음 부분이 좀 햇갈릴 수 있는데,

list.next = new LinkedList();
list.next.value = 2;

1. new LinkedList() (새로운 객체가 만들어집니다)
2. list.next 가 새로운 객체를 가리킵니다
3. list.next 가 가리키는 객체의 value 값에 2를 할당합니다

다음과 같은 순서로 이루어 지고, 그림으로 본다면 다음과 같습니다

 

그림 설명

 

Fig. 2. 맨 오른쪽 새로운 객체 생성

 

Fig. 3. list.next 가 새로운 객체를 가리킴

 

Fig. 4. 새로운 객체 변수 할당

이로 인해 지금 LinkedList 클래스는 다음과 같이 두개의 이어 붙여진 객체를 가지고 있는 것 입니다.

---

다음 포스팅에서 Constructor을 사용해서 객체에 값을 할당하는 것과 LinkedList의 여러가지 메소드에 대해서 알아보겠습니다