자료구조 - 선형 구조: 링크드 리스트

링크드 리스트

연결 리스트라고도 한다. 배열과 달리 랜덤한 위치에 메모리를 할당하여 연결해 배열처럼 사용된다.

---

링크드 리스트 개요

링크드 리스트는 크게 두가지로 나뉜다.

1. 싱글 링크드 리스트
2. 더블 링크드 리스트

연결 방식에 따라 싱글, 더블로 나뉜다. 

링크드 리스트의 경우 변수 하나를 저장하기 위해 2개 ~ 3개의 메모리를 필요로 한다. 하나는 현재 데이터를 저장하기 위한 메모리, 하나는 다음 데이터를 가리키기위한 포인터, 나머지 하나는 이전 데이터를 가리키기 위한 포인터다.

자바로 프로그래밍을 입문한 사람들에겐 포인터가 생소할 수 있다. 자바는 포인터가 없다고 아는 사람들이 많지만, 지금까지 자바를 써온 필자의 생각으론 모든 프로그래밍 언어는 포인터에 베이스를 둔다 생각된다. 

자바로 입문한 미래 개발자를 위해 객체를 통해 설명하도록 하겠다.

간단한 설명은 여기서 마치고 이제 싱글 링크드 리스트, 더블 링크드 리스트를 각 각 살펴보자.

---

싱글 링크드 리스트

싱글 링크드 리스트는 단방향으로 연결 된 링크드 리스트를 말한다. 즉 다음 데이터만을 가리킨다.

위 사진을 보면 데이터와 다음 객체를 가리키는 변수를 갖는 객체를 이어서 만든것을 알 수 있다. C언어의 경우 구조체를 주로 사용하지만 Java를 사용하는 우리는 객체를 통해 구현해야 한다. 

그렇다면 직접 구현해보자.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

Public class Main {
	public class SingleLinkedList {
    	private int data;
        private SingleLinkedList next;
        
        // 생성과 동시에 data 필드에 값을 넣기위한 생성자 설정
        public SingleLinkedList (int data) {
        	this.data = data;
        }
		
        // next 필드가 다음 객체를 가리키기 위한 메서드
        public void setNext(SingleLinkedList next) {
        	this.next = next;
        }
        
        // 다음 객체를 참조하기 위한 get 메서드
        public SingleLinkedList getNext () {
        	return this.next;
        }
        
        // 현재 객체의 data 필드를 참조하기 위한 get 메서드
        public int getData () {
        	return this.data;
        }
    }
    
    public static void main(String args[]) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 입력 횟수 설정
        int size = Integer.parseInt(br.readLine);
        
        // 링크드 리스트의 시작부분 설정 및 첫 객체를 사용하기 위한 헤드의 data필드 설정
        SingleLinkedList head = new SingleLinkedList(Integer.parseInt(br.readLine));
        
        // 실질적으로 링크드 리스트를 구축해 나가는 주체 temp 선언, head에서 부터 시작된다.
        SingleLinkedList temp = head;
        
        // 헤드에 값을 저장해놓은 상태이므로 1부터 시작한다.
        for(int index = 1 ; index < size ; ++index) {
        	//현재 헤드에 값이 저장되어 있으므로, 다음 객체를 생성하고 data 필드를 설정한다.
        	temp.setNext(new SingleLinkedList(Integer.parseInt(br.readLine)));
            
            // 새로 생성된 객체를 참조하도록 temp를 temp의 next 필드로 선언한다.
            temp = temp.getNext();
        }
        
        // 저장된 데이터를 모두 출력하기위해 temp를 head의 위치로 초기화 한다.
        temp = head;
        
        // 마지막 객체의 경우 next필드가 null값이므로 null값이 나오기 전 까지 반복한다.
        while (temp != null) {
        	System.out.println(temp.getData());
            
            // 다음 값을 출력하기 위해 temp를 다음 객체를 참조하도록 초기화 한다.
            temp = temp.getNext();
        }
    }
}

/*
입력:
4
1
3
4
5

출력:
1
3
4
5
*/

코드가 좀 복잡해 보여도 천천히 살펴보면 정말 쉽게 구현이 가능하다. 주석으로 대부분 설명했으므로, 이상의 설명은 생략한다. 

---

듀얼 링크드 리스트

듀얼 링크드 리스트, 이름에서 부터 양방향으로 연결 된 링크드 리스트란 느낌이 팍팍 온다. 싱글과 다르게 next뿐 아닌, prev가 추가되어 이전 항목까지 참조가 가능하다.

위 사진을보면 next는 다음 객체를, prev는 이전 객체를 가리키는것을 볼 수 있다. 싱글 링크드 리스트에서 약간의 변형으로 구현이 가능하다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

Public class Main {
	public class DoubleLinkedList {
    	private int data;
        private DoubleLinkedList prev;
        private DoubleLinkedList next;
        
        // 생성과 동시에 data 필드와 prev 필드를 초기화 하기위한 생성자
        public DoubleLinkedList(int data, DoubleLinkedList prev) {
        	this.data = data;
            this.prev = prev;
        }
        
        public void setPrev (DoubleLinkedList prev) {
        	this.prev = prev;
        }
        
        public void setNext (DoubleLinkedList next) {
        	this.next = next;
        }
        
        public int getData() {
        	return this.data;
        }
        
        public DoubleLinkedList getPrev() {
        	return this.prev;
        }
        
        public DoubleLinkedList getNext() {
        	return this.next;
        }
    }
    
    public static void main(String args[]) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int size = Integer.parseInt(br.readLine());
        
        DoubleLinkedList head = new DoubleLinkedList(Integer.parseInt(br.readLine()), null);
        DoubleLinkedList temp = head;
        
        for(int index = 1 ; index < size ; ++index) {
        	temp.setNext(new DoubleLinkedList(Integer.parseInt(br.readLine()), temp));
            temp = temp.getNext();
        }
        
        temp = head;
        
        // 정방향 검색
        while (temp != null)
        	System.out.println(temp.getData());
            temp = temp.getNext();
        }
        
        // 역방향 검색
        while (temp != null) {
        	System.out.println(temp.getData());
            temp = temp.getPrev();
        }
    }
}

/*
입력:
4
1
3
4
5

출력:
1
3
4
5
5
4
3
1
*/

싱글 링크드 리스트와 비교해서 바뀐 것은 다음과 같다.

1. private DoubleLinkedList prev;

2. public DoubleLinkedList(int data, DoubleLinkedList prev) {}

3. public DoubleLinkedList getPrev () { return this.prev; }

4. while (temp != null) {
        System.out.println(temp.getData());
        temp = temp.getPrev();
}

싱글 링크드 리스트와 비교했을 때, 역방향을 위한 연산 외에는 추가된것이 없다. 싱글 링크드 리스트를 구현할 줄 안다면, 쉽게 구현할 수 있을것이다. 삽입 삭제 연산 기능이 싱글 링크드 리스트에 비해 1단계의 연산이 더 필요한것을 제외하면 구조적으로 같다.

---

링크드 리스트의 장점

1. java 배열의 경우 크기가 정해지면 더이상 늘리거나 줄이는것이 불가능하지만, 링크드 리스트의 경우 자유롭게 설정이 가능하다.
2. 삽입 및 삭제 연산이 비교적 빠르다.
   위 코드에서 구현하지 않았지만, 삽입 삭제 메서드를 구현해 처음, 중간, 끝 어디든 삽입 삭제가 비교적 빠르게 가능하다. temp.next가 참조하는곳만 바꿔주면 된다.

링크드 리스트의 단점

1. 특정 지점의 위치를 잊으면, 특정 위치부터 뒤의 모든 객체를 사용하는것이 불가능에 가깝다. 
   메모리에 연속적으로 할당되는것이 아닌, 랜덤한 위치에 생성되기 때문이다.
2. 배열과 달리 특정 위치의 자료 검색이 느리다.
   예를 들어 7번 째 데이터를 알고 싶다면, 처음부터 7번째 데이터 까지 이동해야 해당 값을 얻을 수 있다.
3. 비교적 알고리즘이 복잡하다.
4. 배열과 다르게 다음 객체를 참조하기 위한 변수가 추가적으로 필요하므로, 메모리 낭비가 발생한다.