[자료구조-PS] Java 에서 단순 연결 리스트 구현하기 :: (Simple Linked List sample code)

단순 연결 리스트

단순 연결 리스트는 가장 단순한 형태의 연결 리스트로 노드가 다음 노드를 가리키는 하나의 참조만 갖고 있으며, 단방향으로 참조할 수 있는 특징 덕분에 구현하기 간단하다.

연결 리스트와 노드 생성

연결 리스트를 만들었으니 삽입과 삭제 연산을 구현해보자.

삽입 연산

삽입 연산은 총 세 가지로 크게 구분할 수 있다.

1. Head에 삽입하기.
2. Tail에 삽입하기.
3. 특정 위치에 삽입하기.

1. Head에 삽입하기

Head에 삽입하기 전에 다음과 같은 과정을 거친다.

1. 새로운 노드 생성
2. 새로운 노드의 다음 노드(link 필드)를 기존에 있던 head노드로 설정
3. 헤드 노드와 새로운 노드의 교환.
4. 테일 노드를 기존의 헤드노드로 설정.

2. Tail에 삽입하기

3. 특정 위치에 삽입하기

특정 위치에 노드를 삽입한다면 우리는 특정 위치를 알아야 한다. 그래서 특정 위치를 찾는 코드를 먼저 구현해보자.
특정 위치를 방법

특정 위치에 노드를 확인하기 위해서 head 노드에서 부터 특정 index만큼 이동한다면 해당 노드가 우리가 찾길 원하는 index 번째 노드가 될 것이다.

특정 위치에 삽입

특정 위지(index)를 지정해주고 특정 위치에 도달하면 기존에 있던 Front Node와 Back Node 사이의 연결을 끊어주고 새로운 노드로 각각 연결 시켜 준다면 된다.

삭제 연산

삭제 연산에는 삽입 연산과 마찬가지로 크게 두 가지로 나눌 수 있다.

1. Head 노드 삭제하기
2. 특정 위치 노드 삭제하기

1. Head 노드 삭제하기

2. 특정 위치 노드 삭제하기

전체 소스 코드

public class Main {
    public static void main(String[] args) {

    }
}

class SimpleLinkedList {

    private Node headNode; // head node
    private Node tailNode; // tail node
    private int size; // list's size

    public SimpleLinkedList(){ // initialize list
        headNode = new Node(null);
        size = 0;
    }

    private class Node { // Node class

        private Object data; // Data Field
        private Node nextNode; // Link Field

        Node (Object data){
            this.data = data;
            nextNode = null;
        }
    }

    /*Head 에 삽입 하기.*/
    void addHead(Object data){

        Node newNode = new Node(data); // Make new Node
        newNode.nextNode = headNode; // set newNode's Link to head
        headNode = newNode; // swap headNode to newNode;
        size++;

        if(headNode.nextNode == null){ // check : Is headNode first
            tailNode =headNode;
        }
    }

    void addTail(Object data){
        if(size == 0){ // if list is empty
            addHead(data);
        }else {
            Node newNode = new Node(data); // Make new Node
            tailNode.nextNode = newNode; // update tail's next
            tailNode = newNode; // swap tailNode to newNode;
            size++;
        }
    }

    /*특정 위치의 노드 찾기*/
    Node node(int index){
        Node x = headNode;
        for (int i = 0; i < index; i++) { // index 까지 반복
            x = x.nextNode;               // 현재 노드에 다음 노드를 할당.
        }
        return x; // 특정 index 의 노드 반환
    }

    void add(Object data, int index){
        if(index == 0) addHead(data);
        else {
            Node temp1 = node(index - 1);
            Node temp2 = temp1.nextNode;

            Node newNode = new Node(data);
            temp1.nextNode = newNode;
            newNode.nextNode = temp2;
            size++;

            if(newNode.nextNode == null){
                tailNode = newNode;
            }
        }
    }

    /*Head 노드 삭제*/
    Object removeHead(){
        Node temp = headNode; // head 에 있는 data 임시 저장
        headNode = temp.nextNode; // headNode 를 기존의 두 번쨰 노드로 바꿔준다.
        /*노드 반환 과정*/
        Object returnData = temp.data;
        temp = null;
        size--;
        return returnData;
    }

    /*Tail 특정 노드 삭제*/
    Object removeNode(int index){
        if(index == 0) {
            removeHead();
        }

        Node temp = node(index -  1); // 특정 위치 전의 노드 찾기
        Node targetNode = temp.nextNode; // temp 노드의 다음 노드가 삭제될 노드
        temp.nextNode = temp.nextNode.nextNode; // temp 노드는 삭제될 다음 노드를 가리킴

        /*노드 반환 과정/
        Object returnData = targetNode.data;a

        if(targetNode == tailNode){
            tailNode = temp;
        }
        targetNode = null;
        size--;
        return returnData;
    }

}