리스트 - LinkedList

LinkedList

 

• 삽입, 삭제, 검색

 

LinkedList의 생김새

 

LinkedList 검색

- 연결리스트는 인덱스를 접근할 수 없기 때문에 검색하기 위해서는 next로 n번 움직여야 한다.

 

LinkedList 추가

LinkedList 삽입

LinkedList 삭제

 

LinkedList의 장점

- 배열의 복사나 재할당없이 데이터 추가 가능

- 유연한 공간

 

LinkedList의 단점

- 데이터 접근에 대한 시간이 늘어남

 

 

읽는데 유리한 자료구조는  Array

 

삭제하고 변경하는데 유리한 자료구조는 LinkedList

 

---

LinkedList 구현

 

- Head 더미 노드를 두면 연결 리스트를 구현하는데 편리하다.

- 연결리스트는 노드 기반이다.

- 노드는 class로 만들어준다.

 

Linked List의 데이터 삽입

- 이전 노드의 next를 새로운 노드를 가르키게 하면 데이터가 삽입이 된다!

 

Linked List의 전체 삭제

정말 빠름 O (1)

그냥 더미 노드인 head의 next를 null로 만들어버리면 모든 리스트가 삭제 된다(연결이 끊어지는것)

public void clear() {
this.size = 0;
this.head.next = null;
}

 

Linked List의 일부 삭제

O (n) 

어떠한 값을 삭제하는 경우 head부터 시작하여, Null을 만날때까지 계속 next로 다음 노드를 접근하여 값이 같은 경우 그 값을 삭제 하지 않고 이전 노드와 다음노드를 연결시켜 현재 노드를 삭제함. 이때 현재 노드의 next를  Null로 가르키도록 만들면 된다.