[자료 구조] - 연결 리스트 자료구조 :: Linked List Data Structure

연결 리스트 Linked List

 

지금까지 우리는 다량의 공통(선형) 데이터를 다루기 위해서 Array, 즉 배열을 많이 써왔다. 배열은 구현이랄 것도 없이 간단하고 쉽게 사용할 수 있지만 치명적인 단점이 있다.

 

바로 연속적인 데이터 저장이다.

 

배열은 data의 element 들이 메모리에 인접한 위치에 저장되거나 메모리에 연이어 저장된다.

 

이러한 점이 배열을 생성하고 삭제, 삽입하는 과정에서 큰 오버헤드를 가져올 수 있기 때문에 우리는 LinkedList를 배워야 하는 이유이다.

 

배열과 연결 리스트의 차이점

 

연결 리스트는 그림에서도 보이듯이 비연속적 위치에 각각의 데이터들이 다음 데이터를 연결하고 있다.

 

Node

 

연결 리스트에는 노드라는 개념이 있다. 이 노드에 우리는 데이터를 넣고 다음 데이터를 찾을 수 있게 하는 주소 참조를 확인할 수 있다.

 

노드의 구조

 

노드는 두 가지의 필드로 구성된다.

 

1. Data Field
2. Link Field

 

Data Field

 

데이터 필드라고 불리는 곳은 실제 값 Actual Value이 저장되는 부분이다.

 

Link Field

링크 필드라고 불리는 곳은 다음 노드를 가리키는 위치(주소)Address 포인터이다.

 

 

이러한 노드의 구조 덕분에 우리는 선형 데이터를 Array처럼 연속되는 공간에 저장하지 않아도 되고, 물리적으로 떨어진 곳에 저장할 수 있게된다.

 

연결 리스트의 구조

 

연결 리스트는 다음과 같이 3 가지의 큰 파트가 존재한다.

 

 

1. Head Node
2. Body Node
3. Tail Node

1. Head Node

헤드 포인터라고도 불리는 이 부분은 연결 리스트의 시작 지점을 뜻한다.

 

2. Body Node

헤드 포인터에 의해 접근되며, 데이터를 담고 있는 부분이다.

 

3. Tail Node

Tail 노드는 연결 리스트의 마지막 부분을 뜻하고 통상적으로 Null을 가리키고 리스트에 데이터가 마지막이라는 것을 알려준다.

 

연결 리스트의 연산

 

연결 리스트에 있는 기본적 연산은 삽입 연산과 삭제 연산이다.

 

1. 삽입 연산

 

삽입 연산의 순서는 다음과 같다.

 

1. 노드 생성
2. 삽입할 위치 지정
3. 삽입할 위치에 전 노드의 링크 필드를 삽입할 노드의 주소로 설정
4. 삽입할 노드의 링크 필드를 삽입하기 전 위치에 있던 마지막 노드로 설정
5. 삽입

2. 삭제 연산

 

삭제 연산의 순서는 다음과 같다.

 

1. 삭제할 노드 지정
2. 삭제할 위치의 전 노드에 링크 필드를 삭제할 노드의 다음 노드의 링크 필드로 지정
3. 삭제

연결 리스트의 3 가지 종류

1. 단순 연결 리스트
2. 원형 연결 리스트
3. 이중 연결 리스트

1. 단순 연결 리스트

단순 연결 리스트는 위에서 설명했던 일반적인 리스트이다. Head 포인터로 시작하여 Tail 포인터가 Null을 가리키고 있는 일반적인 모습의 연결리스트 이다.

2. 원형 연결 리스트

원형 연결 리스트는 Tail 노드가 Head 노드를 참조하고 있는 형태이다.

3. 이중 연결 리스트

이중 연결 리스트는 노드에 다음 주소를 가리키는 Link Field 를 두 개를 만들어서 앞 전 노드와 다음 노드를 한 번에 가리키는 모습이다.

구현

public class Main {

    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        list.add(11);
        list.add(33);

        list.add(1, 22);

        list.print();

        list.remove();

        list.print();

        System.out.println(list.get(0) + " ");
    }
}

class MyNode {
    private int data; // 실제 값, actual value
    private MyNode nextNode; // 다음 노드를 가리키는 위치(주소) 포인터

    MyNode(int data) {
        this.data = data;
        this.nextNode = null;
    }

    void setNextNode(MyNode nextNode) {
        this.nextNode = nextNode;
    }

    MyNode getNextNode() {
        return nextNode;
    }

    int getData() {
        return data;
    }
}

class LinkedList {
    private MyNode headNode;

    LinkedList() {
        headNode = null;
    }

    // 마지막에 노드 추가
    void add(int data) {
        MyNode newNode = new MyNode(data);

        if(headNode == null) { // head 포인터가 없을 때, 연결 리스트가 비어있을 때
            this.headNode = newNode;
        }else { // head 포인터가 존재할 때, 연결 리스트에 데이터가 있을 때
            MyNode pointerNode = headNode;

            while(pointerNode.getNextNode() != null) {
                pointerNode = pointerNode.getNextNode();
            }
            pointerNode.setNextNode(newNode);
        }
    }

    // 특정 인덱스에 노드 추가
    void add(int index, int data) {
        MyNode newNode = new MyNode(data);
        if(headNode == null) {
            headNode = newNode;
        }else {
            MyNode pointerNode = headNode;
            while(index > 1) {
                pointerNode = pointerNode.getNextNode();
            }
            // 인덱스가 마지막 노드일 경우
            if(pointerNode.getNextNode() == null) {
                pointerNode.setNextNode(newNode);
            }else {
                // 새로운 노드가 가리키는 노드는 이전에 연결된 노드
                MyNode preNode = pointerNode;
                newNode.setNextNode(preNode.getNextNode());
            }
            pointerNode.setNextNode(newNode);
        }
    }

    void remove() {

        MyNode pointerNode = headNode;
        MyNode previousNode = pointerNode;

        if(headNode == null) {
            return;
        }

        if(headNode.getNextNode() == null) {
            headNode = null;
        } else {
            while(pointerNode.getNextNode() != null) {
                previousNode = pointerNode;
                pointerNode = pointerNode.getNextNode();
            }

            previousNode.setNextNode(null);
        }
    }


    int get(int index) {
        MyNode pointerNode = this.headNode;

        if(headNode == null) {
            return -1;
        }else {
            while(index-- > 0) {
                pointerNode = pointerNode.getNextNode();
            }
            return pointerNode.getData();
        }
    }

    void print() {
        MyNode pointerNode = this.headNode;
        int index = 0;

        while(pointerNode != null) {
            System.out.println("index: " + index + " data: " + pointerNode.getData());
            pointerNode = pointerNode.getNextNode();
            index++;
        }
    }
}