[김영한의 실전 자바 - 중급 2편] 04. 컬렉션 프레임워크 - LinkedList

Turtle·2024년 7월 8일
김영한의 실전 자바 - 중급 2편
0

[인프런 강의] 김영한의 실전 자바 - 중급 2편

목록 보기
4/10
post-thumbnail

🏷️노드와 연결

public class Node {
	Object item;
	Node next;

	public Node(Object item) {
		this.item = item;
	}

	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		Node x = this;
		sb.append("[");
		while (x != null) {
			sb.append(x.item);
			if (x.next != null) {
				sb.append("→");
			}
			x = x.next;
		}
		sb.append("]");
		String string = sb.toString();
		return string;
	}
}
public class NodeMain3 {
	public static void main(String[] args) {
		Node first = new Node("A");
		first.next = new Node("B");
		first.next.next = new Node("C");

		printAll(first);
		Node lastNode = getLastNode(first);
		System.out.println(lastNode);

		Node getNode = getNode(first, 2);
		System.out.println(getNode);
		add(first, "D");
		Node resultNode = getLastNode(first);
		System.out.println(resultNode);

	}

	// 마지막에 노드 추가하기
	private static void add(Node first, String param) {
		Node lastNode = getLastNode(first);
		lastNode.next = new Node(param);
	}

	// 특정 인덱스의 노드 찾기
	private static Node getNode(Node first, int index) {
		Node x = first;
		for (int i = 0; i < index; i++) {
			x = x.next;
		}
		return x;
	}

	// 마지막 노드 찾기
	private static Node getLastNode(Node first) {
		Node x = first;
		while (x.next != null) {
			x = x.next;
		}
		return x;
	}

	// 모든 노드 탐색하기
	private static void printAll(Node first) {
		Node x = first;
		while (x != null) {
			System.out.println(x.item);
			x = x.next;
		}
	}
}
  • ✔️정리
    • 노드는 내부에 데이터와 다음 노드에 대한 참조를 가지고 있다.
    • 지금까지 설명한 구조는 각각의 노드가 참조를 통해 연결되어있다.
    • 데이터를 추가할 때 동적으로 필요한 만큼의 노드만 만들어서 연결하면 된다. 따라서 배열과 다르게 메모리를 낭비하지 않는다.
      • 물론 next 필드를 통해 처음 참조값을 보관해야 하기 때문에 배열과 비교해서 추가적인 메모리 낭비도 발생한다.
    • 각각의 노드를 연결해서 자료 구조로 리스트를 만들 수 있는데, 이것을 연결리스트라 한다.

🏷️직접 구현하는 연결 리스트1 - 시작

연결 리스트는 배열 리스트의 단점인 메모리 낭비, 중간 위치 데이터 추가에 대한 성능 문제를 어느 정도 극복할 수 있다.

public class MyLinkedListV1 {
	private Node first;
	private int size = 0;

	public void add(Object o) {
		Node node = new Node(o);
		if (first == null) {
			first = node;
		} else {
			Node lastNode = getLastNode();
			lastNode.next = node;
		}
		size++;
	}

	public Node getLastNode() {
		Node x = first;
		while (x.next != null) {
			x = x.next;
		}
		return x;
	}

	public Object get(int index) {
		Node x = first;
		for (int i = 0; i < index; i++) {
			x = x.next;
		}
		return x.item;
	}

	public Object set(int index, Object element) {
		Node node = getNode(index);
		Object oldValue = node.item;
		node.item = element;
		return oldValue;
	}

	public Node getNode(int index) {
		Node x = first;
		for (int i = 0; i < index; i++) {
			x = x.next;
		}
		return x;
	}

	public int indexOf(Object o) {
		int index = 0;
		for (Node x = first; x != null; x = x.next) {
			if (o.equals(x.item)) {
				return index;
			}
			index++;
		}
		return -1;
	}

	@Override
	public String toString() {
		return "MyLinkedListV1{" +
				"first=" + first +
				", size=" + size +
				'}';
	}

	public int size() {
		return size;
	}
}
public class MyLinkedListV1Main {
	public static void main(String[] args) {
		MyLinkedListV1 myLinkedListV1 = new MyLinkedListV1();
		System.out.println("==데이터 추가==");
		System.out.println(myLinkedListV1);
		myLinkedListV1.add("a");
		System.out.println(myLinkedListV1);
		myLinkedListV1.add("b");
		System.out.println(myLinkedListV1);
		myLinkedListV1.add("c");
		System.out.println(myLinkedListV1);

		System.out.println("==기능 사용==");
		System.out.println("myLinkedListV1.size() " + myLinkedListV1.size());
		System.out.println("myLinkedListV1.get() = " + myLinkedListV1.get(2));
		System.out.println("myLinkedListV1.indexOf() " + myLinkedListV1.indexOf("b"));
		System.out.println("myLinkedListV1.set(), oldValue = " + myLinkedListV1.set(1, "f"));
		System.out.println(myLinkedListV1);

		System.out.println("==범위 초과==");
		myLinkedListV1.add("d");
		System.out.println(myLinkedListV1);
		myLinkedListV1.add("e");
		System.out.println(myLinkedListV1);

		myLinkedListV1.add("g");
		System.out.println(myLinkedListV1);
	}
}
  • ✔️연결리스트와 빅오
    • Object get(int index) : 특정 위치에 있는 데이터를 반환한다. → O(N)
      • 배열은 인덱스로 원하는 데이터를 즉시 찾을 수 있다. 따라서 배열을 사용하는 배열 리스트의 경우 인덱스로 조회시 O(1)의 빠른 성능을 보장한다. 하지만 연결 리스트에서 사용하는 노드들은 배열이 아니다. 단지 다음 노드에 대한 참조가 있을 뿐이다. 따라서 인덱스로 원하는 위치의 데이터를 찾으려면 인덱스 숫자만큼 다은 노드를 반복해서 찾아가야 한다. 따라서 인덱스 조회 성능이 나쁘다.
      • 특정 위치의 노드를 찾는데 O(N)이 걸린다.
    • void add(Object o) : 마지막에 데이터를 추가한다. → O(N)
      • 마지막 노드를 찾는데 O(N)이 소요된다. 마지막 노드에 새로운 노드를 추가하는데 O(1)이 걸린다. 따라서 O(N)이다.
    • Object set(int index, Object element) : 특정 위치에 있는 데이터를 찾아서 변경한다. 그리고 기존 값을 반환한다. → O(N)
      • 특정 위치의 노드를 찾는데 O(N)이 걸린다.
    • int indexOf(Object o) : 데이터를 검색하고 검색된 위치를 반환한다. → O(N)
      • 모든 노드를 순회하면서 equals()를 사용해서 같은 데이터가 있는지 찾는다.

🏷️직접 구현하는 연결 리스트 - 추가와 삭제

public class MyLinkedListV2 {
	private Node first;
	private int size = 0;

	public void add(int index, Object o) {
		Node newNode = new Node(o);
		if (index == 0) {
			newNode.next = first;	// 신규 노드와 다음 노드 연결
			first = newNode;		// first에 신규 노드 할당
		} else {
			Node prev = getNode(index - 1);
			newNode.next = prev.next;	// 직전 노드의 참조값을 새로운 노드에 할당해야함
			prev.next = newNode;		// 직전 노드에 신규 노드를 할당
		}
		size++;
	}

	public Object remove(int index) {
		Node removedNode = getNode(index);
		Object o = removedNode.item;
		if (index == 0) {
			first = removedNode.next;
		} else {
			Node node = getNode(index + 1);
			Node prev = getNode(index - 1);
			prev.next = node;
		}
		removedNode.item = null;
		removedNode.next = null;
		size--;
		return o;
	}

	public void add(Object o) {
		Node node = new Node(o);
		if (first == null) {
			first = node;
		} else {
			Node lastNode = getLastNode();
			lastNode.next = node;
		}
		size++;
	}

	public Node getLastNode() {
		Node x = first;
		while (x.next != null) {
			x = x.next;
		}
		return x;
	}

	public Object get(int index) {
		Node x = first;
		for (int i = 0; i < index; i++) {
			x = x.next;
		}
		return x.item;
	}

	public Object set(int index, Object element) {
		Node node = getNode(index);
		Object oldValue = node.item;
		node.item = element;
		return oldValue;
	}

	public Node getNode(int index) {
		Node x = first;
		for (int i = 0; i < index; i++) {
			x = x.next;
		}
		return x;
	}

	public int indexOf(Object o) {
		int index = 0;
		for (Node x = first; x != null; x = x.next) {
			if (o.equals(x.item)) {
				return index;
			}
			index++;
		}
		return -1;
	}

	@Override
	public String toString() {
		return "MyLinkedListV1{" +
				"first=" + first +
				", size=" + size +
				'}';
	}

	public int size() {
		return size;
	}
}
public class MyLinkedListV2Main {
	public static void main(String[] args) {
		MyLinkedListV2 myLinkedListV2 = new MyLinkedListV2();
		System.out.println("==데이터 추가==");
		myLinkedListV2.add("a");
		myLinkedListV2.add("b");
		myLinkedListV2.add("c");
		System.out.println(myLinkedListV2);

		System.out.println();

		System.out.println("==첫 번째 데이터 추가==");
		myLinkedListV2.add(0, "d");
		System.out.println(myLinkedListV2);

		System.out.println();

		System.out.println("==첫 번째 데이터 삭제==");
		Object removedNode1 = myLinkedListV2.remove(0);
		System.out.println(removedNode1);
		System.out.println(myLinkedListV2);

		System.out.println();

		System.out.println("==중간에 데이터 추가==");
		myLinkedListV2.add(1, "e");
		System.out.println(myLinkedListV2);

		System.out.println();

		System.out.println("==중간에 데이터 삭제==");
		Object removedNode2 = myLinkedListV2.remove(2);
		System.out.println(removedNode2);
		System.out.println(myLinkedListV2);
	}
}
  • ✔️정리
    • 배열 리스트는 인덱스를 통해 추가나 삭제할 위치를 O(1)으로 빠르게 찾을 수 있으나 추가나 삭제 이후 데이터를 한 칸씩 이동시켜야 한다. 이 부분이 O(N)으로 오래 걸린다.
    • 반면에 연결 리스트는 인덱스를 통해 추가나 삭제할 위치를 O(N)으로 느리게 찾지만 찾은 이후에는 일부 노드의 참조값만 변경하면 되므로 이 부분이 O(1)으로 빠르다.
    • 앞에 추가하는 경우 연결 리스트는 배열 리스트처럼 추가한 항목의 오른쪽에 있는 데이터를 모두 한 칸씩 밀지 않아도 된다. 단순히 일부 노드 참조만 변경하면 된다. 따라서 데이터를 앞쪽에 추가하는 경우 연결 리스트가 더 좋은 성능을 제공한다.
      • 배열 리스트 : 데이터를 앞쪽에 추가하면 이후의 데이터를 모두 오른쪽으로 밀어야 한다. → O(N)
      • 연결 리스트 : 데이터를 앞쪽에 추가하면 일부 노드 참조값만 변경하면 된다. → O(1)
    • 마지막에 추가하는 경우 배열 리스트는 인덱스로 마지막 위치를 바로 찾을 수 있다. 데이터를 마지막에 추가하는 경우 데이터를 이동시킬 필요가 없다. 연결 리스트의 경우 노드를 마지막까지 순회해야 마지막 노드를 찾을 수 있다.
      • 배열 리스트 : 인덱스로 마지막 위치를 즉시 찾아O(1) 데이터를 마지막에 추가하는 경우 데이터를 이동하지 않아도 된다.O(1) 따라서 O(1)의 성능을 제공한다.
      • 연결 리스트 : 노드를 마지막까지 순회해야 마지막 노드를 찾을 수 있다. 따라서 마지막 노드를 찾는데 O(N)의 시간이 소요된다. 여기서 데이터를 추가하는 경우는 O(1)이다. 따라서 O(N)의 성능을 제공한다.
  • ✔️결론
    • 데이터를 조회할 일이 많고 뒷부분에 데이터를 추가한다면 인덱스를 활용할 수 있어 O(1) 내로 해결할 수 있는 배열 리스트가 더 좋고 앞쪽의 데이터를 추가하거나 삭제할 일이 많은 경우 추가나 삭제 후 데이터의 이동이 불필요한 연결 리스트를 사용하는 것이 더 좋다.

🏷️직접 구현하는 연결 리스트 - 제네릭 도입

public class MyLinkedListV3<E> {
	private Node<E> first;
	private int size = 0;

	public void add(int index, E o) {
		Node<E> newNode = new Node(o);
		if (index == 0) {
			newNode.next = first;	// 신규 노드와 다음 노드 연결
			first = newNode;		// first에 신규 노드 할당
		} else {
			Node prev = getNode(index - 1);
			newNode.next = prev.next;	// 직전 노드의 참조값을 새로운 노드에 할당해야함
			prev.next = newNode;		// 직전 노드에 신규 노드를 할당
		}
		size++;
	}

	public E remove(int index) {
		Node<E> removedNode = getNode(index);
		E o = removedNode.item;
		if (index == 0) {
			first = removedNode.next;
		} else {
			Node<E> node = getNode(index + 1);
			Node<E> prev = getNode(index - 1);
			prev.next = node;
		}
		removedNode.item = null;
		removedNode.next = null;
		size--;
		return o;
	}

	public void add(E o) {
		Node<E> node = new Node(o);
		if (first == null) {
			first = node;
		} else {
			Node<E> lastNode = getLastNode();
			lastNode.next = node;
		}
		size++;
	}

	public Node<E> getLastNode() {
		Node<E> x = first;
		while (x.next != null) {
			x = x.next;
		}
		return x;
	}

	public E get(int index) {
		Node<E> x = first;
		for (int i = 0; i < index; i++) {
			x = x.next;
		}
		return x.item;
	}

	public E set(int index, E element) {
		Node<E> node = getNode(index);
		E oldValue = node.item;
		node.item = element;
		return oldValue;
	}

	public Node<E> getNode(int index) {
		Node<E> x = first;
		for (int i = 0; i < index; i++) {
			x = x.next;
		}
		return x;
	}

	public int indexOf(E o) {
		int index = 0;
		for (Node<E> x = first; x != null; x = x.next) {
			if (o.equals(x.item)) {
				return index;
			}
			index++;
		}
		return -1;
	}

	public int size() {
		return size;
	}

	@Override
	public String toString() {
		return "MyLinkedListV3{" +
				"first=" + first +
				", size=" + size +
				'}';
	}

	private class Node<E> {
		E item;
		Node<E> next;

		public Node(E item) {
			this.item = item;
		}

		@Override
		public String toString() {
			StringBuilder sb = new StringBuilder();
			Node x = this;
			sb.append("[");
			while (x != null) {
				sb.append(x.item);
				if (x.next != null) {
					sb.append("→");
				}
				x = x.next;
			}
			sb.append("]");
			String string = sb.toString();
			return string;
		}
	}
}
public class MyLinkedListV3Main {
	public static void main(String[] args) {
		MyLinkedListV3<String> stringMyLinkedListV3 = new MyLinkedListV3<>();
		System.out.println("==데이터 추가==");
		stringMyLinkedListV3.add("a");
		stringMyLinkedListV3.add("b");
		stringMyLinkedListV3.add("c");
		System.out.println(stringMyLinkedListV3);

		System.out.println("==중간에 데이터 추가==");
		stringMyLinkedListV3.add(1, "f");
		System.out.println(stringMyLinkedListV3);

		System.out.println("==중간에 데이터 삭제==");
		String removed1 = stringMyLinkedListV3.remove(1);
		System.out.println(removed1);
		System.out.println(stringMyLinkedListV3);

		System.out.println("==데이터 삭제==");
		String removed2 = stringMyLinkedListV3.remove(0);
		System.out.println(removed2);
		System.out.println(stringMyLinkedListV3);
	}
}
  • ✔️결론
    • 제네릭 덕분에 타입 안전성을 보장하는 자료구조를 만들 수 있다.
profile
Turtle
이전 포스트

[김영한의 실전 자바 - 중급 2편] 03. 컬렉션 프레임워크 - ArrayList

다음 포스트

[김영한의 실전 자바 - 중급 2편] 05. 컬렉션 프레임워크 - List

0개의 댓글