[자료구조 JAVA] Singly LinkedList 구현하기

List 는 데이터들이 기차처럼 일렬로 나열되어 있는 자료구조를 의미합니다.

기차는 머리부분과 몸통, 꼬리부분으로 이루어져 있습니다.

기차의 구조처럼, 연결 리스트 또한 머리(Head)와 꼬리(Tail)가 있고, 머리와 꼬리, 그리고 이들 사이에 자료를 저장해요.

현실에선 앞 에서부터 1호차, 2호차, 3호차, ... 순으로 부르고 이 안에 사람들이 들어가죠?

이를 일반화해서 Node라는 클래스를 만들어볼까요?

 

사전지식

Generic: https://www.yunki.kr/69

 

1. Node<T>

class Node<T> {
    private Node<T> next;
    private T data;

    public Node(T data) {
        this.data = data;
        this.next = null;
    }
}

멤버의 역할은 다음과 같습니다.

next	자신과 연결된 다음 호차를 기억하기 위한 주소(레퍼런스)
data	그리고 데이터를 담을 공간

그리고 데이터를 저장하기 위한 생성자와 getter,setter 함수가 필요해 보입니다.

class Node<T> {
    private Node<T> next;
    private T data;

    public Node(T data) {
        this.data = data;
        this.next = null;
    }

    public Node<T> getNext() {
        return next;
    }

    public void setNext(Node<T> next) {
        this.next = next;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                '}';
    }
}

 

2. 연결리스트의 장단점

class LinkedList<T> {
    private Node<T> head = null;
    private Node<T> tail = null;
    private int size = 0;

    public int size() {
        return this.size;
    }
}

1). 장점 - head와 tail이 필요한 이유

List라는 자료구조는 삽입 삭제가 빠르다는 장점이 있습니다. 왜 그럴까요?

삽입이 빠른 이유는 무조건 가장 뒤에 추가하면 되기 때문입니다. 그래서 tail이 필요한 것이지요!

 

삭제가 빠른 이유는 삭제할 노드의 이전 노드와 다음 노드를 연결해주면 끝이기 때문입니다!

배열은 중간에 값을 삭제하려면, 재할당이 필요하고 기존을 값을 복사해야하기 때문에. 비효율적입니다.

 

2). 단점 - 검색이 느림

배열은 연속된 메모리 공간을 할당 받기 때문에, 인덱스[] 로 접근이 가능하지만, 연결 리스트의 경우에는 그렇지 않습니다. 메모리가 띄엄 띄엄 할당이 되어 있죠!

그래서 next 를 타고 타고 일일이 확인을 해야합니다. 그래서 검색이 느려요!

 

따라서 빠른 검색을 위한 자료구조로는 적합하지 않습니다. 이럴 경우 배열을 쓰거나 어레이 리스트를 써야할 것입니다.

 

3. 메소드 구현

1). 추가

2). 검색

3). 삭제

이번 글에서는 위의 세 기능을 구현해볼 것입니다.

시작해볼까요?

 

1). 추가 ( add )

데이터를 추가하기 위해서는 2단계의 검증과 3단계의 연산이 필요합니다.

1. 데이터가 null  이라면? 삽입 불가!

2. head 가 null 이라면? 리스트가 비어있었다는 의미이므로 newNode를 head로 선언합니다.

3. head 가 존재한다면? 적어도 1개 이상의 노드가 존재하므로 마지막 노드(tail)에 새 노드를 이어 붙이면 됩니다.

4. tail 을 newNode로 갱신합니다.

5. 리스트의 사이즈를 1 증가시킵니다.

public void add(T data) {
    if (data == null) {
        return;
    }
    
    if (head == null) {
        head = new Node<T>(data);
        tail = head;
    } else {
        Node<T> newNode = new Node<T>(data);
        tail.setNext(newNode);
        tail = newNode;
    }
    size++;
}

두 번째 삽입부터는 tail에 붙으면 되니 삽입이 엄청 빨라지겠죠? ^^

 

2). 검색 ( find )

검색은 서두에 말씀드렸듯이, 느리다고 했습니다. 그 이유는 검색을 위해서 head 부터 next 링크를 타고 찾아가야 하기 때문이죠. 못 찾았을 경우에는 예외를 발생시키면 좋을 것 같네요~ 자 이제, 생각해보죠!

1. 링크를 타고 타고 하는 방법은 검색을 위한 iter 노드를 만들고 여기에 head를 가리키도록 준비한다음.

2. while 문으로 iter 가 자신의 다음 노드를 가리키도록 하면 됩니다. ( iter = iter.getNext() )

그러다 iter의 데이터 값이 찾고자하는 값과 같으면 이 값을 돌려주면 되겠죠?

만약, 리스트의 끝까지 갔는데도 찾지 못 했다면, 예외를 던져주면 될 것 같습니다.

public Node<T> find(T data) throws Exception {
	Node<T> iter = head;
	while (iter != null && iter.getData() != data) {
		iter = iter.getNext();
	}

	if (iter == null) {
		throw new Exception(data+"은 리스트에 존재하지 않습니다.");
	}

	return iter;
}

 

3). 삭제 ( delete )

마지막으로 삭제 연산을 생각해보겠습니다.

삭제는 검색과 상당히 유사합니다.

1. 삭제할 노드를 찾았을 경우에는

2. 그 자리에서 즉시 멈춘 다음, 자신의 이전노드가 <- [자신의] -> 다음 노드를 가리키게 하면 되겠죠?

3. 여기서 리스트가 텅텅 비어있을 수도 있고, 삭제하려고 했던 값이 할당을 못 받아 null 이었다면, 문제가 발생하겠죠?

리스트에 존재하지 않는 걸 지우려고 했기 때문이니까요~ 이 부분은 삭제전에 예외처리를 해줘야합니다!

public boolean delete(T deleteMe) throws Exception {
	Node<T> iter = head;

	if(head == null || deleteMe == null) return false;

	if (head.getData() == deleteMe) {
		head = iter.getNext();
		iter = null;
		
        	size--;
		return true;
	}

	while (iter != null) {
		if (iter.getNext().getData() == deleteMe) {
			Node<T> temp = iter.getNext();
			iter.setNext(temp.getNext());
			temp = null;

			size--;
			return true;
		}
	
    		iter = iter.getNext();
	}

	return false;
}

내가 삭제하고자 하는 노드를 B, B의 이전을 A, B의 다음을 C라고 해보겠습니다. 그럼 다음과 같은 관계가 있음을 알 수 있어요!

A	B	C
iter	iter.next	iter.next.next

A는 현재 탐색중인 노드인 iter 를 가리키고, B는 iter의 다음 노드가 되고, 우리는 이 B값이 우리가 삭제할 deleteMe 랑 같은지를 검사할거예요! 

자 그런데, 코드에서는 이런 표현을 눈을 씻고 찾아봐도 없죠? 그 이유는 temp 라는 노드를 써서 iter.next 를 치환해뒀기 때문입니다. 그럼 다음과 같이 더 간단히 나타낼 수 있겠죠?

A	B	C
iter	temp	temp.next

이제 삭제를 위해 다음의 과정을 거쳐야합니다.

1. while(iter != null) 일 때까지 iter = iter.getNext() 로 탐색을 합니다.

2. iter.getNext().getData() 값이 deleteMe와 같다면, 탐색을 중지하고 삭제를 실시합니다.

3. 삭제할 노드를 미리 null 로 바꿔버리면, 연결정보가 같이 사라지게 되겠죠! 그러므로 temp에 저장해둡니다.

Node<T> temp = iter.getNext();

 

4. 삭제하고자 하는 노드를 temp에 저장해둔 시점에, iter는 삭제하려는 노드의 이전 노드를 가리키고 있습니다.(iter=A)

따라서 A와 C를 연결해주면 되는데. 이를 코드로 나타내면,

      A--------------C               

iter.setNext( temp.getNext() ) 가 되겠죠?

 

5. A와 C가 연결되었으니, 이제 B를 삭제하면 됩니다.

B = null <=> temp = null;

 

6. 마지막으로 사이즈를 하나 감소시켜줍시다.

 

class Node<T> {
    public Node<T> next;
    public T data;

    public Node(T data) {
        this.data = data;
        this.next = null;
    }

    public Node<T> getNext() {
        return next;
    }

    public void setNext(Node<T> next) {
        this.next = next;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                '}';
    }
}

class LinkedList<T> {
    private Node<T> head = null;
    private Node<T> tail = null;
    private int size = 0;

    public void add(T data) {
        if (data == null) {
            return;
        }

        if (head == null) {
            head = new Node<T>(data);
            tail = head;
        } else {
            Node<T> newNode = new Node<T>(data);
            tail.setNext(newNode);
            tail = newNode;
        }
        size++;
    }

    public Node<T> find(T data) throws Exception {
        Node<T> iter = head;
        while (iter != null && iter.getData() != data) {
            iter = iter.getNext();
        }

        if (iter == null) {
            throw new Exception(data+"은 리스트에 존재하지 않습니다.");
        }

        return iter;
    }

    public boolean delete(T deleteMe) throws Exception {
        Node<T> iter = head;

        if(head == null || deleteMe == null) return false;

        if (head.getData() == deleteMe) {
            head = iter.getNext();
            iter = null;
            size--;

            return true;
        }

        while (iter != null) {
            if (iter.getNext().getData() == deleteMe) {
                Node<T> temp = iter.getNext();
                iter.setNext(temp.getNext());
                temp = null;

                size--;
                return true;
            }
            iter = iter.getNext();
        }

        return false;
    }

    public int size() {
        return this.size;
    }
}


public class LinkedListTest {
    public static void main(String[] args) throws Exception {
        LinkedList<Integer> list = new LinkedList<>();

        // 삽입
        for (int i = 0; i < 5; i++) {
            list.add(i);
        }

        // 찾기
        System.out.println(list.find(0));
//        System.out.println(list.find(5));

        // 삭제
        list.delete(4);
        System.out.println(list.size());

        // 헤드 삭제시 검색
        System.out.println(list.find(4));
    }
}