🧑🏻‍💻 Singly LinkedList 직접 구현 (JAVA)

1. Singly LinkedList 자료구조

https://ming412.tistory.com/157

Array vs LinkedList 특징 & 성능 비교

 

2. Singly LinkedList 직접 구현하기

1) ADT (Abstract Data Type) 정의

- 데이터 (Data)

    - Node

        - data: 데이터

        - next: 다음 노드를 참조

    - MySinglyLinkedList

        - head: 연결 리스트의 처음 요소를 참조

        - size: 연결 리스트의 길이

 

- 작업 (Operation)

    - search(idx): 특정 위치의 노드 반환

    - addFirst(e): 연결리스트 맨 앞에 노드 추가

    - addLast(e): 연결리스트 맨 마지막에 노드 추가

    - add(idx, e): 특정 위치에 노드 추가

    - get(idx): 특정 위치의 노드의 값 반환

    - remove(idx): 특정 위치의 요소 삭제

 

2) Node 클래스 정의

data 변수로 값을 저장하고, next로 다음 노드의 주소를 참조한다.

public class Node<E> {
	public E data; // 데이터
	public Node<E> next; // 다음 노드의 주소

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

 

3) MySinglyLinkedList 클래스 정의

직접 구현한 단일 링크드 리스트는 head 포인터로 첫 번째 노드의 주소를 참조하고, size 변수로 리스트의 전체 길이를 가지고 있다.

public class MySinglyLinkedList<E> {
	private Node<E> head;
	private int size;

	public MySinglyLinkedList() {
		this.head = null;
		this.size = 0;
	}
}

 

4) search 구현

search는 add와 remove에서 사용될 내부 메서드이다.

add와 remove를 하기 위해서는, 먼저 추가/삭제할 요소를 탐색해야 하기 때문에 search 메서드가 반복적으로 재사용될 것이다.

public Node<E> search(int idx) {
    Node<E> cur = head;
    for (int i=0; i<idx; i++) {
        cur = cur.next;
    }
    return cur;
}

 

5) add 구현

addFirst - 리스트의 맨 처음에 요소를 추가한다.

이때 head가 null이 아닌 경우는 리스트에 다른 원소가 이미 존재하는 상태이다.

이때는 head를 갱신하기 전에, 새로운 노드의 next에 기존 head를 대입하여 둘을 미리 연결해 놓아야 한다. 

public void addFirst(E e) {
    Node<E> newNode = new Node<>(e);
    if (head != null) {
        // 새로운 노드와 기존 첫 번째 노드를 연결
        newNode.next = head;
    }
    // head를 새로운 노드로 갱신
    head = newNode;
    size++;
}

 

addLast - 리스트의 맨 끝에 요소를 추가한다.

리스트가 비어있지 않다면, 앞서 만들었던 search 함수를 이용해 연결리스트의 맨 마지막 노드를 찾는다.

그리고 그 노드와 새로운 노드를 연결한다.

 

만약 리스트가 비어있다면 head를 새로운 노드로 갱신한다.

public void addLast(E e) {
    Node<E> newNode = new Node<>(e);
    if (head != null) {
        // 맨 마지막 노드를 찾기
        Node<E> lastNode = search(size - 1);
        // 맨 마지막 노드와 새로운 노드를 연결
        lastNode.next = newNode;
    } else {
        head = newNode;
    }
    size++;
}

 

add - 리스트의 특정 위치에 요소를 추가한다.

우선, 추가 위치(idx)를 검증한다.

idx가 연결리스트 사이즈보다 클 때에는 예외 처리를 한다.

 

그리고 idx가 0이거나 size일 때는 미리 만들어둔 addFirst와 addLast를 활용한다.

 

idx가 0또는 size가 아니라면,

search 함수를 이용해서 바로 앞 노드(prev)를 찾고, 새로 추가할 노드와 prev의 다음 노드를 먼저 연결해야 한다.

그리고 prev의 다음 노드를 새로 추가할 노드로 갱신한다.

public void add(int idx, E e) {
    Node<E> newNode = new Node<>(e);
    if (idx > size || idx < 0) {
        throw new IndexOutOfBoundsException();
    }
    else if (idx == 0) {
        addFirst(e);
    }
    else if (idx == size) {
        addLast(e);
    } else {
        // 바로 앞 노드를 찾기
        Node<E> prevNode = search(idx - 1);
        // 새로운 노드와 prev의 next 연결
        newNode.next = prevNode.next;
        // prev의 next 갱신
        prevNode.next = newNode;
    }
}

 

6) remove 구현

특정 위치의 노드를 제거한다는 것은, 그 노드의 연결을 끊는다는 것이다.

그러기 위해 제거할 노드의 앞 노드와 제거할 노드가 필요하다.

제거할 노드의 앞 노드와 제거할 노드의 다음 노드를 서로 연결해주면 제거할 노드는 연결이 끊어지게 된다.

public void remove(int idx) {
    if (idx >= size || idx < 0) {
        throw new IndexOutOfBoundsException();
    } else {
        // 바로 앞 노드를 찾기
        Node<E> prevNode = search(idx - 1);
        // 제거할 노드를 찾기
        Node<E> targetNode = search(idx);
        // 바로 앞 노드와 제거할 노드의 다음 노드를 연결
        prevNode.next = targetNode.next;
    }
}

 

7) get 구현

get 함수는 특정 위치의 노드를 찾아 그 값을 반환하면 된다.

미리 만들어둔 search 함수를 이용하면 되고, idx의 범위까지 검증하자.

public E get(int idx) {
    if (idx >= size || idx < 0) {
        throw new IndexOutOfBoundsException();
    }
    return search(idx).data;
}

 

8) toString 오버라이딩

아래처럼 toString을 오버라이딩하면 디버깅하기 좋다.

@Override
public String toString() {
    Node<E> cur = head;
    while (cur != null) {
        System.out.print(cur.data + " ");
        cur = cur.next;
    }
    System.out.println();
    return "MySinglyLinkedList{" +
        "head.data=" + head.data +
        ", size=" + size +
        '}';
}

 

9) 전체 코드

public class MySinglyLinkedList<E> {
	private Node<E> head;
	private int size;

	public MySinglyLinkedList() {
		this.head = null;
		this.size = 0;
	}

	public Node<E> search(int idx) {
		Node<E> cur = head;
		for (int i=0; i<idx; i++) {
			cur = cur.next;
		}
		return cur;
	}

	public void addFirst(E e) {
		Node<E> newNode = new Node<>(e);
		if (head != null) {
			// 새로운 노드와 기존 첫 번째 노드를 연결
			newNode.next = head;
		}
		// head를 새로운 노드로 갱신
		head = newNode;
		size++;
	}

	public void addLast(E e) {
		Node<E> newNode = new Node<>(e);
		if (head != null) {
			// 맨 마지막 노드를 찾기
			Node<E> lastNode = search(size - 1);
			// 맨 마지막 노드와 새로운 노드를 연결
			lastNode.next = newNode;
		} else {
			head = newNode;
		}
		size++;
	}

	public void add(int idx, E e) {
		Node<E> newNode = new Node<>(e);
		if (idx > size || idx < 0) {
			System.out.println("Index: " + idx + ", Size: " + size);
		}
		else if (idx == 0) {
			addFirst(e);
		}
		else if (idx == size) {
			addLast(e);
		} else {
			// 바로 앞 노드를 찾기
			Node<E> prevNode = search(idx - 1);
			// 새로운 노드와 prev의 next 연결
			newNode.next = prevNode.next;
			// prev의 next 갱신
			prevNode.next = newNode;
		}
	}

	public void remove(int idx) {
		if (idx >= size || idx < 0) {
			throw new IndexOutOfBoundsException();
		} else {
			// 바로 앞 노드를 찾기
			Node<E> prevNode = search(idx - 1);
			// 제거할 노드를 찾기
			Node<E> targetNode = search(idx);
			// 바로 앞 노드와 제거할 노드의 다음 노드를 연결
			prevNode.next = targetNode.next;
		}
	}

	public E get(int idx) {
		if (idx >= size || idx < 0) {
			throw new IndexOutOfBoundsException();
		} else {
			return search(idx).data;
		}
	}

	@Override
	public String toString() {
		Node<E> cur = head;
		while (cur != null) {
			System.out.print(cur.data + " ");
			cur = cur.next;
		}
		System.out.println();
		return "MySinglyLinkedList{" +
			"head.data=" + head.data +
			", size=" + size +
			'}';
	}
}

public class Main {
	public static void main(String[] args) {
		MySinglyLinkedList<String> linkedList = new MySinglyLinkedList<>();
		linkedList.addFirst("A");
		linkedList.addLast("B");
		linkedList.addLast("C");
		System.out.println(linkedList.toString());

		linkedList.add(0, "D");
		linkedList.add(4, "E");
		System.out.println(linkedList.toString());

		linkedList.remove(3);
		System.out.println(linkedList.toString());
	}
}

실행 결과