[자료구조] LinkedList 구현

주재완·2024년 3월 13일

자료구조

목록 보기

3/10

Introduction

ArrayList를 전 포스팅에서 구현하였습니다.

우선, 또다른 대표적인 list인 LinkedList에 대해서 알아봅니다. 그리고 LinkedList를 좀 더 명확하게 구현한 버전과, 코딩 테스트 실전용으로 구현한 두 가지 방법으로 구현하고자 합니다. (삼성 B형 대비)

LinkedList?

일반배열과는 접근법이 다릅니다. LinkedList의 경우에는 노드(Node)가 일렬로 배치되는 형태로 구성되어 있습니다. 또한 각 노드는 데이터와 포인터를 가지고 있습니다. 데이터는 말 그대로 저장된 값을 의미하고, 포인터는 (1) 이전 노드의 주소를 가진 포인터와 (2) 다음 노드의 주소를 가진 포인터로 구성되어 있습니다. 아래 그림과 같은 구조를 가지고 있다 생각하면 편합니다.

LinkedList

이와 같이 data와 prev, next라는 포인터를 가지고 있는 노드들끼리 연결된 것을 확인할 수 있습니다. 정확히 위와 같은 형태의 LinkedList는 이중 연결 리스트입니다. prev포인터 없이 단일 포인터로만 LinkedList 구현도 가능한데 이를 단일 연결 리스트입니다. 실제 Java Collections에는 이중 연결 리스트로 구현되어 있기도 하고, 자료를 검색하는데 단일 연결 리스트에 비해 시간복잡도는 O(N)으로 동일하지만 최악의 경우 수행 횟수는 차이가 납니다. 이는 바로 아래 접근, 검색, 삽입, 삭제에서 언급하도록 하겠습니다.

접근 및 검색

접근 및 검색을 하는 방법은 시작점 또는 끝점부터 시작하여 순차적으로 하나씩 접근합니다. 그런데 시작점과 끝점은 어떻게 판별이 가능할까요? 바로 prev와 next, 즉 포인터로 판별합니다. 바로 아래와 같은 기준으로 판별합니다. 조금만 생각해보면 직관적으로 알 수 있습니다.

시작점 : prev = null;
끝점 : next = null;

단일 연결 리스트는 직접 시작점을 정해줍니다. 그리고 next 포인터를 사용해 그다음 노드로 계속 넘어가는 타입입니다. 여기서 소개하는 이중 연결 리스트의 경우 prev 포인터가 있어 역방향으로도 진행이 가능합니다.

물론 둘다 시간 복잡도를 비교하면 순차비교기에 O(N)이기는 합니다만, 최악의 케이스에서 이중 연결 리스트가 유리합니다. 자료가 1000개 있다고 가정할 때 999번째를 찾는다면 단일 연결 리스트는 999회의 반복, 이중 연결 리스트는 뒤에서 부터 확인이 가능하므로 단 1회의 반복으로 조회가 가능합니다. 또한 예시에서 확장하여 이중 연결 리스트의 최악은 앞뒤를 모두 확인하기에 500회를 넘지 않을 것입니다.

삽입과 삭제

연결리스트는 삽입과 삭제에 아주 큰 장점이 있습니다. 기존 배열은 새로운 배열 생성으로 시간복잡도가 O(N) 걸리는 것을 연결리스트는 단 O(1)으로(제일 앞이나 뒤에 넣는 경우), ArrayList같이 (amortized)O(1)도 아닌 그냥 O(1)으로 가능합니다.

삽입

삽입은 다음과 같은 과정으로 이루어집니다.

새로운 노드를 우선 생성합니다. (포인터 변수명의 경우 앞 노드는 pprev, pnext, 새 노드는 prev, next, 다음 노드는 nprev, nnext 로 가정)

prev에는 앞 노드의 주소를, next에는 뒷 노드의 주소를 저장합니다.

pnext, nprev에는 새로운 노드의 주소를 저장합니다.

즉 기존의 연결을 끊어서 새로운 노드와 연결하되, 먼저 새 노드의 포인터로 먼저 앞 노드와 뒷 노드 주소를 저장한 뒤, 기존의 연결을 끊는 방식을 사용합니다.

삭제

삭제는 삽입의 역순입니다.

삭제는 다음과 같은 과정으로 이루어집니다.

(포인터 변수명의 경우 앞 노드는 pprev, pnext, 삭제할 노드는 prev, next, 다음 노드는 nprev, nnext 로 가정)
1. pnext에는 뒷 노드 주소를 저장, nprev에는 앞 노드의 주소를 저장합니다.
2. 삭제할 노드의 prev, next에는 모두 null을 넣어 연결을 끊어줍니다.

구현

MyList Interface

메소드를 사용할 때 ArrayList<>()와 기능이 동일합니다. 이 때 사용했던 인터페이스를 그대로 들고 왔습니다.

package com.example.list;

public interface MyList<E> {
	
	void add(E e);
    
    void add(int index, E e);
	
	boolean contains(E e);
	
	E get(int index);
	
	int indexOf(E e);
	
	void remove(int index);
	
	void set(int index, E e);
	
	int size();
}

각 메소드, 즉 List의 핵심 기능은 다음과 같습니다.

add(E e) : 요소를 맨 끝에 추가합니다.
add(int index, E e) : 해당 인덱스 위치에 요소를 넣습니다.
contains(E e) : 요소가 있는지 확인합니다.
get(int index) : 해당 인덱스에 해당하는 값을 반환합니다.
indexOf(E e) : 해당 요소의 인덱스를 반환합니다. 없으면 -1을 반환합니다.
remove(int index) : 해당 인덱스에 해당하는 값을 삭제합니다.
set(int index, E e) : 해당 인덱스에 해당하는 값을 수정합니다.
size() : 리스트의 크기를 반환합니다.

MyLinkedList class

자바에서는 포인터 개념은 없습니다. 대신 구현할 수 있는 방법은 노드 클래스를 만들어서 클래스 내부에 본인을 타입으로 하는 객체를 두개 만들어서 진행합니다. 이 객체 두개가 바로 포인터 역할을 합니다.

package com.example.list;

public class MyLinkedList<E> implements MyList<E>{
	private int size;
	private ListNode head;
	private ListNode tail;
	
	class ListNode {
		E data;
		ListNode prev;
		ListNode next;
		
		ListNode(E data, ListNode prev, ListNode next) {
			this.data = data;
			this.prev = prev;
			this.next = next;
		}
	}
	
	public MyLinkedList() {
		this.size = 0;
		this.head = null;
		this.tail = null;
	}
	
	public void addFirst(E e) {
		ListNode first = this.head;
		ListNode newNode = new ListNode(e, null, first);
		head = newNode;
		if(first == null) {
			tail = newNode;
		} else {
			first.prev = newNode;
		}
		size++;
	}
	
	public void addLast(E e) {
		ListNode last = this.tail;
		ListNode newNode = new ListNode(e, last, null);
		tail = newNode;
		if(last == null) {
			head = newNode;
		} else {
			last.next = newNode;
		}
		size++;
	}
	
	/**
	 * 기본적으로 List에 값이 있다고 가정, size가 0인 경우는 없음.
	 * @return 첫번째 노드 값
	 */
	public E pollFirst() {
		ListNode first = this.head;
		if(first.next == null) {
			head = null;
			tail = null;
		} else {
			head = first.next;
			first.next.prev = null;
		}
		size--;
		return first.data;
	}
	
	/**
	 * 기본적으로 List에 값이 있다고 가정, size가 0인 경우는 없음.
	 * @return 마지막 노드 값
	 */
	public E pollLast() {
		ListNode last = this.tail;
		if(last.prev == null) {
			head = null;
			tail = null;
		} else {
			tail = last.prev;
			last.prev.next = null;
		}
		size--;
		return last.data;
	}
	
	ListNode node(int index) {
		ListNode node = null;
		if (index < (size >> 1)) {
			node = head;
			for(int i = 0; i < index; i++) {
				node = node.next;
			}
		} else {
			node = tail;
			for(int i = size - 1; i > index; i--) {
				node = node.prev;
			}
		}
		return node;
	}

	@Override
	public void add(E e) {
		this.addLast(e);
	}

	@Override
	public void add(int index, E e) {
		ListNode next = node(index);
		ListNode prev = next.prev;
		ListNode newNode = new ListNode(e, prev, next);
		
		if(index == size + 1) {
			this.addLast(e);
		} else if(index == 0) {
			this.addFirst(e);
		} else {
			prev.next = newNode;
			next.prev = newNode;
			size++;
		}
	}

	@Override
	public boolean contains(E e) {
		return indexOf(e) != -1;
	}

	@Override
	public E get(int index) {
		return node(index).data;
	}

	@Override
	public int indexOf(E e) {
		int index = 0;
		for(ListNode node = head; node != null; node = node.next) {
			if(node.data.equals(e)) {
				return index;
			}
			index++;
		}
		return -1;
	}

	@Override
	public void remove(int index) {
		ListNode node = node(index);
		if(index == 0) {
			pollFirst();
		} else if(index == size - 1) {
			pollLast();
		} else {
			(node.prev).next = node.next;
			(node.next).prev = node.prev;
			size--;
		}
	}

	@Override
	public void set(int index, E e) {
		ListNode node = node(index);
		node.data = e;
	}

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

	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		sb.append("[");
		for(int i = 0; i < this.size - 1; i++) {
			sb.append(node(i).data).append(", ");
		}
		if(this.size >= 0) sb.append(node(this.size - 1).data);
		sb.append("]");
		return sb.toString();
	}
}

검사

package com.example.list;

public class MyLinkedListRun {
	public static void main(String[] args) {
		MyLinkedList<String> list = new MyLinkedList<>();
		
		// toString 체크
		list.add("first");
		System.out.println(list.toString()); // [first]
		
		list.add("second");
		System.out.println(list.toString()); // [first, second]
		
		// index 인자가 있는 add 체크
		list.add(0, "head");
		list.add(4, "tail");
		list.add(2, "new Second");
		System.out.println(list); // [head, first, new Second, second, tail]
		
		// contains 체크
		System.out.println(list.contains("second")); // true
		System.out.println(list.contains("third")); // false
		
		// get 체크
		System.out.println(list.get(2)); // new Second
		
		// remove 체크
		list.remove(4);
		list.remove(0);
		list.remove(1);
		System.out.println(list.toString()); // [first, second]
		
		// set 체크
		list.set(0, "zero");
		System.out.println(list.toString()); // [zero, second]
		
		// size 체크
		System.out.println(list.size()); // 2
	}
}

구현(Simple)

삼성 B형과 같이 라이브러리가 제한된 코딩 테스트를 대비해서 실전으로 사용할만한 LinkedList 역시 생각하였습니다.

package com.example.list;

/*
 * 코딩 테스트 용으로 구성된 간단한 LinkedList
 * add(), remove(), get()으로 구성
 * 단일 연결 리스트로 구성
 * 데이터로 정수가 들어온다고 가정
 * 헤드를 추가적인 노드로 생성, 그 헤드 다음부터 인덱스 0로 시작
 */
class Node {
	int data;
	Node next;
	
	public Node(int data) {
		this.data = data;
		this.next = null;
	}
	
	/**
	 * 전해준 노드 뒤에 데이터를 집어넣는 메소드
	 * @param prev 데이터를 집어넣는 곳 앞에 있는 노드
	 * @param data 데이터
	 */
	public static void add(Node prev, int data) {
		Node node = new Node(data);
		Node next = prev.next;
		
		prev.next = node;
		node.next = next;
	}
	
	/**
	 * 전달받은 값(데이터)에 해당하는 모든 노드 삭제
	 * @param head LinkedList의 처음
	 * @param data 데이터
	 */
	public static void remove(Node head, int data) {
		Node prev = null;
		for(Node n = head; n != null; n = n.next) {
			if(n.data == data) {
				Node next = n.next;
				prev.next = next;
			}
			prev = n;
		}
	}
	
	/**
	 * 해당 인덱스의 노드를 반환
	 * @param head LinkedList의 처음
	 * @param index 인덱스
	 * @return Node
	 */
	public static Node get(Node head, int index) {
		Node node = head.next;
		for(int i = 0; i < index; i++) {
			node = node.next;
		}
		return node;
	}
}

public class MyLinkedListSimple {
	public static void main(String[] args) {
		// 헤드, 0이라는 데이터는 dummy data (size == 0)
		Node head = new Node(0); 
		
		// add()
		Node.add(head, 1);
		System.out.println(list(head)); // 1
		
		Node.add(head, 2);
		System.out.println(list(head)); // 2 1
		
		Node last = Node.get(head, 1);
		Node.add(last, 2);
		System.out.println(list(head)); // 2 1 2
		
		Node node = Node.get(head, 0);
		Node.add(node, 3);
		System.out.println(list(head)); // 2 3 1 2
		
		// get()
		for(int i = 0; i < 4; i++) {
			System.out.print(Node.get(head, i).data);
			System.out.print("|");
		} 
		System.out.println(); // 2|3|1|2|
		
		// remove()
		Node.remove(head, 2);
		System.out.println(list(head)); // 3 1
		
		Node.remove(head, 3);
		System.out.println(list(head)); // 1
	}
	
	public static String list(Node head) {
		StringBuilder sb = new StringBuilder();
		for(Node n = head.next; n != null; n = n.next) { 
			sb.append(n.data).append(" ");
		}
		return sb.toString();
	}
}