서론

• 링크드 리스트에 대해서 어떻게 동작하는지 원리를 알아봅니다.
• 컬렉션 Api가 아닌 직접 구현해서 한번 더 이해해봅니다.

---

본론

링크드 리스트 구조 💁🏻

• 연결 리스트라고도 한다.
• 배열은 순차적으로 연결된 공간에 데이터를 나열하는 구조
• 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조

배열의 큰 단점 💁🏻

• 데이터가 어디까지 저장이 될지 모르니 처음에 공간을 할당해주어야 한다.

데이터가 추가가 되면 배열이 자동으로 추가가 되면 얼마나 좋을까 ? ⇒ 이것을 고민한게 링크드 리스트

링크드 리스트의 노드(하나의 데이터)는 단순 하나로만 이뤄진게 아닌 데이터를 저장할 데이터를 위한 공간과, 다음 데이터 주소를 저장할 공간 이렇게 두개를 할당 후 데이터를 삽입한다. (주소용 데이터는 Null로 표기가 된다.)

새로 데이터가 저장되면 기존에 주소를 저장하는 공간은 데이터의 주소를 할당하고, 또 두번째 노드는 데이터 데이터 주소용 공간을 할당한다. (각 데이터의 공간이 쭉 이어져 있지 않아도, 데이터의 순서를 알 수 있다.)

링크드 리스트의 장단점 💁🏻

• 장점 : 미리 공간을 할당하지 않아도 된다. (배열은 미리 공간을 할당해야한다.) 하지만 항상 데이터를 저장할때 데이터 공간 + 다음 데이터주소 를 저장하기때문에 낭비적인 요소가 존재한다.
• 단점 : 링크드리스트는 데이터를 저장/삭제 할때마다 앞의 데이터로 이동해서 뒤 데이터의 주소를 저장하는 부가적인 로직이 필요하다. 접근 속도가 느리고 저장공간 효율이 높지 않다.

링크드 리스트 기본 구조와 용어 💁🏻

• 노드 : 데이터 저장 단위 (데이터값, 포인터) 로 구성
• 포인터 : 각 노드 안에서 다음이나 이전의 노드와의 연결 정보를 갖고 있는 공간.

기본적인 노드 클래스를 구현해본다. 👇🏻

public class Node<T> { //노드 구현
T data; //제네릭 타입
Node<T> next = null; //포인터

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

링크드 리스트가 어떻게 동작하는지 코드로 직접 작성해보자. 👇🏻

Node<Integer> node1 = new Node<Integer>(1); //각각 노드 생성
Node<Integer> node2 = new Node<Integer>(2);

node1.next= node2; //포인터 연결  (다만 이렇게만 하면 **어떤 노드가 맨 앞인지** 모른다.)
Node head = node1; //맨 앞에있는 노드를 넣어주면 간편히 탐색이 가능하다.

링크드 리스트를 직접 구현해보자. 👇🏻

public class SingleLinkedList<T>{
 public Node<T> head = null; 

  public class Node<T>{
		T data;
		Node<T> next = null;
	 public Node(T data){
		 this.data = data;
	}
}
	  public void addNode(T data){
		if(head == null){ //첫 노드
			head = new Node<T>(data); //객체를 새로 넣어준다.
		} else{ //노드가 존재한다면?
			Node<T> node = this.head; //현재 head 노드를 넣는다.
				while(node.next!= null){ //그 다음 노드가 존재할때 현재 노드를 그 다음노드로 바꿔준다.
			node = node.next;}
		node.next = new Node<T>(data);
				} //next 가 null이라면 현재 링크드 리스트의 마지막을 알 수 있다.
			}
		}

구현한 링크드 리스트를 사용해보자. 👇🏻

SingleLinkedList<Integer> MyLinkedList = new SingleLinkedList<Integer>();
MyLinkedList.addNode(1); //1 노드가 head에 저장된다.
MyLinkedList.head.data -> 1 (data를 쓰지 않으면 객체가 출력된다.)

MyLinkedList.addNode(2);
MyLinkedList.head.next.data -> 2

출력 메소드를 선언해보자. 👇🏻

public void printAll(){
	if(head!=null){ //head노드가 null이면 출력하지 않는다.
		Node<T> node = this.head;//head 노드부터 출력 
		System.out.println(node.data);
		while(node.next!=null){ //포인터가 존재한다면 ?
			node = node.next;  //다음 노드를 가져와 출력한다.
			System.out.println(node.data);
					}
			}
	}
}

기존에 구현한 싱글 링크드 리스트의 살짝 아쉬운점 ⇒ head 노드부터 탐색하기 때문에, 만약 100개의 노드가 존재하는 리스트의 99번째 인덱스를 가져오려면 99번을 일일히 탐색해야 한다. 🤔

|→ 해당 수고를 덜어주는 더블 링크드 리스트가 존재한다. 💁🏻

• 이중 연결 리스트라고도 한다.
• 장점 : 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능하다.

더블 링크드 리스트를 구현해보자. 👇🏻

public class DoubleLinkedList<T> {
	public Node<T> head = null;
	public Node<T> tail = null; //이번엔 끝을 지정하는 필드변수가 들어간다.
	
	public class Node<T>{
		T data;
		Node<T> prev =null; //앞을 연결하는 포인터가 생겼다.
    Node<T> next =null;
		
		public Node(T data){
			this.data = data;
			}
	}

	public void addNode(T data){
			if(this.head ==null){ 
				this.head = new Node<T>(data);
				this.tail = this.head; //첫 노드는 헤드,테일 둘다 같다.
			}else{ //null이 아니라면?
			Node<T> node = this.head; //첫 노드를 가져온다.
			while(node.next!=null){ //두번째 노드가 존재한다면?
					node = node.next;  // 돌고 돌고 돈다.
					} //도는게 끝나면?
					node.next = new Node<T>(data); //null 일때 새로 들어온 데이터를 입력
					node.next.prev = node; //포인터의 전 노드를 해당 노드로 입력해준다.
			}
		}
}

해당 더블 링크드 리스트로도 앞에서 혹은 뒤에서 출력하는 메소드를 구현 할 수도 있다.

만약에 원하는 데이터의 자리에 새로운 데이터를 삽입하고 싶다면 ?

• 해당 링크드 리스트가 원소를 갖지 않을 때 ⇒ head,tail 둘다 새로 삽입한 원소를 참조하게 한다.
• 원소를 갖고 있고 삽입을 원하는 인덱스가 첫번째일 때 ⇒ head 원소를 가져온 후, head 의 prev에 새 원소를 참조시키고, 새 원소의 next 에 head 를 참조시킨 뒤, head 에 새 원소를 참조시킨다.
• 리스트의 중간에 삽입을 원할 때 ⇒ 리스트를 탐색해서 해당 노드를 가져온 후, 해당 노드의 앞 노드를 가져온다. → 앞 노드의 next에 새로운 노드를 넣어주고 새 노드의 next 에 기존 인덱스에 존재하는 노드를 넣어준다. → 새 노드의 prev에 앞노드를, next에 뒷노드를, 그리고 기존노드의 prev에 새 노드를 넣어준다.

이런식으로 구현이 가능하다. (그림을 그리면서 이해하면 좋다.)

---

마무리

• 링크드 리스트가 왜 알고리즘에서 이용할때 속도가 느렸는지 드디어 이해할 수 있게 되었습니다.

• 구현되어있는 api를 직접 구현해보니,아 이렇게 우리를 위해 노력해준 윗 선배님들에게 무한한 감사를 느끼게 됩니다.

• api 하나를 사용하더라도 원리를 알고 사용한다면 더더욱 효율적으로 성능을 끌어 올릴 수 있는 프로그래밍을 할 수 있을것 같다는 생각이 들었습니다.

• 각각 휴대폰에 맞는 케이스와 상황에 맞는 재질의 각각 다른 케이스가 존재하듯이, 하나하나 해당 자료구조를 사용할때 그 자료구조를 선택한 이유가 존재해야 할 것 같다는 깨닳음을 얻었습니다.