Data Structure - Linked List (2)

1. Linked List - 특정 노드 삭제

- 특정 노드를 삭제하는 경우는 3가지가 있다(첫노드, 중간노드, 마지막노드). 이를 배워보기 전에 베이스로 이용할 연결리스트를 코드로 작성한다. 

- 위의 코드를 기반으로 3가지 노드 삭제 경우를 처리하기 위한 delete메소드를 작성한다. 

 

 

a) head 노드 삭제

 

 

b) 마지막 노드 삭제 & 중간 노드 삭제

---

2. 다양한 Linked List 구조 - Double Linked List

- 연결리스트의 단점은 대용량 자료검색이 힘들다는 점이다. 그 이유는 노드마다 다음 노드의 주소값을 갖고 있기 때문에 1만개의 노드 중 가장 8000번째 노드를 찾는다면 0부터 7999번까지 모든 자료를 보아야 한다. 이런 단점을 해결하기 위해 연결리스트는 다양한 구조로 구현한다. 

 

a) Double Linked List 구조

- 1만개 data로 이루어진 연결리스트에서 8000번째 노드를 찾는다면 0번부터 검색하는 것이아니라 마지막 노드인 1만번째 노드부터 검색하는 것이 훨씬 빠르다. 이를 가능하게 하는 것이 이중 연결리스트이다. 

 

- 일반 연결리스트는 data와 다음 노드의 주소값 갖고 있는 구조이다. 이중 연결리스트는 현재 노드의 data를 기준으로 이전 노드와 다음 노드의 주소값 두개를 갖고 있는 구조이다. 이를 코드로 구현해보자. 

 

- 위의 코드와 기존의 연결리스트의 코드를 비교하여 어떤 차이가 있는지 공부하는 것이 중요하다. 

---

b) Double Linked List 메소드 구현 - head 노드부터 검색

- Double Linked List구조를 만든 코드의 desc메소드 아래에 이어서 작성하면 됩니다. 

 

 

 

 

[테스트 - 검색 결과가 있을 때]

 

[테스트 - 검색 결과가 없을 때]

---

c) Double Linked List 메소드 구현 - tail 노드부터 검색 

- head노드부터 검색하는 메소드와 큰 차이가 없습니다. head대신 tail을 next대신 prev를 사용하면 됩니다. 

 

 

 

 

[테스트 - 검색 결과가 있을 때]

 

 

[테스트 - 검색 결과가 없을 때]

---

d) Double Linked List 메소드 구현 - 특정 노드 이전에(prev) 노드를 삽입

- 특정 노드의 이전 노드자리에 삽입하는 것이니까 마지막 노드부터 거꾸로 검색하는 것이 좋겠죠?

- 코드의 전체적인 흐름을 주석으로 표시해 놓았으니 필요하신 분들은 참고하시길 바랍니다. 

 

 

[테스트 - 2를 검색해서 1.5를 삽입한다.]

 

 

1) 이중연결리스트 생성 

 

 

2) 메소드 실행 후 결과 출력 및 검색 메소드로 잘 연결되었는지 검사

---

e) Double Linked List 메소드 구현 - 특정 노드 다음에(next) 노드를 삽입

- 위의 코드와 비슷하겠죠? tail부터가 아니라 head부터 검색하고 prev가 아니라 next로 바꿔주면 됩니다. 

 

 

[테스트 - 3을 검색해서 3.5를 삽입한다.]

 

1) 이중연결리스트 생성 

 

 

2) 메소드 실행 후 결과 출력 및 검색 메소드로 잘 연결되었는지 검사