노드와 연결

배열 리스트 단점

배열 리스트는 내부에 배열을 사용해서 필요한 배열의 크기를 미리 확보해야 한다. 데이터가 얼마나 추가될지 예측 할 수 없는 경우 나머지 공간은 사용되지 않고 낭비된다.

배열의 중간에 데이터 추가

배열의 앞이나 중간에 데이터를 추가하는 경우 추가할 데이터의 공간을 확보하기 위해 기존 데이터들을 오른쪽으로 이동해야 한다. 이처럼 앞이나 중간에 데이터를 추가 또는 삭제하는 경우 많은 데이터를 이동시켜야 해 성능이 좋지 않다.

노드와 연결

낭비되는 메모리 없이 딱 필요한 만큼만 메모리를 확보해서 사용하고, 또 앞이나 ㅈ우간에 데이터를 추가하거나 삭제할 때 노드를 사용해 각 노드를 연결하면 문제가 해결된다.

• Node 인스턴스를 생성하고 item에 A를 넣는다.
• Node 인스턴스를 생성하고 item에 B를 넣는다.
• 이후 처음 만든 노드의Node next필드에 새로 만든 노드의 참조값을 넣어준다.
• 이렇게 하면 첫번째 노드와 두번째 노드가 연결되어 첫번째 노드의 node.next를 호출하면 두번째 노드를 구할 수 있다.
• Node 인스턴스를 생성하고 item 에 "C"를 넣어준다.
• 두 번째 만든 노드의 Node next 필드에 새로 만든 노드의 참조값을 넣어준다.
• 이렇게하면 두 번째 노드와 세 번째 노드가 서로 연결된다.
  
  

직접 구현하는 연결 리스트

public void add(Object e) {

          Node newNode = new Node(e);
          if (first == null) {
              first = newNode;
          } else {
              Node lastNode = getLastNode();
              lastNode.next = newNode;
          }
		  size++; 
      }
private Node getLastNode() {
          Node x = first;
		while (x.next != null) {
        x = x.next; 
        }
		return x; 
     }
     

• first값이 null이면 new Node 를 first값으로 지정
• first값이 not null이면 노드의 마지막 값을 가지고와 그 노드의 next값을 new node값으로 지정

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

• getNode(int index)메서드로 입력받은 인덱스 위치의 노드값 반환
• get(int index)메서드로 입력받은 인덱스 위치의 노드 객체 item값 반환

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;
}

• 노드 객체의 아이템을 마지막 노드가 될때까지 비교, 비교 중 입력받은 값과 일치하면 index값 반환후 for문 종료

연결 리스트와 빅오

Object get(int index)

• 특정 위치에 있는 데이터를 반환한다.
• O(n)
  • 배열은 인덱스로 원하는 데이터를 즉시 찾을 수 있지만 , 연결 리스트에서 사용하는 노드들은 배열이 아니라 단지 다음 노드에 대한 참조값이 있을 뿐이다.
  • 따라서 인덱스로 원하는 위치의 데이터를 찾으려면 인덱스의 숫자만큼 다음 노드를 반복해서 찾아야 하므로 O(n)의 성능을 가진다.

void add(Object o)

• 마지막에 데이터를 추가한다.
• O(n)
  • 특정 위치의 노드를 찾는데 O(n)이 걸린다.

int indexOf(Object o)

• 데이터를 검색하고, 검색된 위치를 반환한다.
• O(n)
  • 모든 노드를 순회하면서 equals()를 사용해서 같은 데이터가 있는지 찾는다.

메서드 추가

void add(int index,Object e)

• 특정 위치에 데이터를 추가한다.
• 내부에서 노드도 함께 추가된다.

Object remove(int index)

• 특정 위치에 있는 데이터를 제거한다.
• 내부에서 노드도 함께 제거된다.

첫 번째 데이터 추가

• 배열의 경우 첫 번째 항목에 데이터가 추가되면 모든 데이터를 오른쪽으로 하나씩 밀어야 하지만 연결 리스트는 새로 생성한 노드의 참조값만 변경하면 된다.
• 연결 리스트의 첫 번째 항목에 값을 추가하는 것은 O(1)로 표현할 수 있다.

첫 번째 데이터 삭제

• 배열의 경우 첫 번째 항목이 삭제되면 모든 데이터를 왼쪽으로 하나씩 밀어야 하지만 연결 리스트는 일부 참조만 변경하면 된다.
• 연결 리스트의 첫 번째 값을 삭제하는 것은 O(1)로 표현할 수 있다.

중간 위치 데이터 추가

• 배열과 다르게 모든 데이터가 이동하지는 않지만, 지정된 인덱스의 노드를 찾는데 시간이 걸린다.
• O(n)의 성능이다.
  • 연결 리스트는 인덱스를 사용해서 노드를 추가할 위치를 찾는데 O(n)
  • 찾은 인덱스에 데이터를 추가하는데 O(1)
  • 결과적으로 O(n)

중간 위치 데이터 삭제

• O(n)의 성능이다.
  • 연결리스트에서 삭제한 인덱스의 노드를 찾는데 O(n)이 걸림
  • 찾은 인덱스 노드 이전의 참조값을 변경하는데 O(1)이 걸림
  • 결과적으로 O(n)

실제 코드

public void add(int index, Object e) {
    Node newNode = new Node(e);
    if (index == 0) {
        newNode.next = first;
        first = newNode;
    } else {
        Node prev = getNode(index - 1);
        newNode.next = prev.next;
        prev.next = newNode;
	}
	size++; 
}

• index==0이면 새롭게 생성한 노드 값의 다음을 first로 변경
• index!=0이면 index-1 위치의 노드값 파악
• index-1값 다음의 노드를 새로 생성한 노드의 next값으로, 새로 생성한 노드의 prev값을 index-1 노드의 값으로 설정

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

• index==0이면 첫번째 값을 제거하겠다는 의미이므로 first값을 removeNode.next값으로 함
• index!=0이먄 입력받은 인덱스 이전의 노드값을 구한 후 인덱스 이전의 노드 next를 removeNode.next값으로 설정
• 이후 removeNode값을 모두 초기화

배열 리스트 VS 연결 리스트 사용

데이터를 조회할 일이 많고 뒷 부분에 데이터를 추가한다면 배열리스트가 더 좋은 성능을 제공한다.
앞쪽의 데이터를 추가하거나 삭제할 일이 많다면 연결리스트를 사용하는 게 보통 더 좋은 성능을 제공한다.








출처: https://www.inflearn.com/course/%EA%B9%80%EC%98%81%ED%95%9C%EC%9D%98-%EC%8B%A4%EC%A0%84-%EC%9E%90%EB%B0%94-%EC%A4%91%EA%B8%89-2/dashboard