안녕하세요 Dibrary입니다.
이번에 정리해볼 자료구조는 리스트 입니다.
일반적으로 리스트란 일련의 동일한 타입의 항목을 의미.
뭔 소리냐하믄, 비슷한 것을 줄줄이 소세지 마냥 엮어 놓은 것이라 보면 됩니다.
근데 우리는 이미 비슷한 자료구조를 알고 있죠? 배열. 배열과의 차이는 뭘까요?
배열은 데이터가 연속으로 위치해 있고, 리스트는 그럴수도 있고 아닐수도 있다는 것입니다.
리스트를 잘 보시면 군데군데 꼭 붙어있지 않더라도 연결을 해서 하나의 '배열 처럼' 만들었죠?
이렇게 떨어진 곳의 데이터를 하나의 '배열 처럼' 다루고자 하는 것이 리스트 자료구조 입니다.
보면 데이터 1개마다 1개의 화살표로 다음 데이터를 이어줬는데 한 방향입니다. 이렇게 만든 것이 단순연결리스트 이고,이 화살표가 양방향이라면 이중연결리스트가 됩니다.
그러면 먼저 단순연결리스트를 구현해보겠습니다. 구현 언어는 파이썬을 사용하겠습니다. 앞으로도 자료구조는 파이썬을 이용할 것입니다.
리스트 구현에 앞서 노드를 코드로 구현해 보겠습니다.
노드는 딱 전달인자로 2개만 받습니다. 해당 노드가 가지는 값과, 다음 노드로 향하는 '화살표' 를 self.next로 만든 것입니다.
화살표는 곧 다음 노드로 '갈수 있음'을 의미합니다.
따라서, 여기서는 self.next라는 속성으로 저장해두고 필요할 때 마다 사용할 수 있고, 이는 언제든 다음 노드로 '갈수 있음'이 됩니다.
과연 그런지 테스트를 해보겠습니다.
임의로 3개의 노드를 만든 후에, 1번 뒤에는 2번, 2번 뒤에는 3번을 연결해 두었습니다.
1번 노드만을 가지고 next.next.value를 확인하니 3번 노드의 값을 확인할 수 있네요. 연결이 된 것을 알 수 있습니다.
근데, 위 코드는 Node를 일일이 각각 입력하고 이어줘야 한다는 단점이 있습니다.
즉, 이것은 아직 자료'구조'가 아닙니다. 구조를 보기만 한 것이지 형태를 갖춘게 아닙니다.
리스트가 이미 갖춰진 상태에서 수정이 이뤄질 수도 있겠죠?
이 이미지를 보면 위에 없던 7이라는 값이 추가되었죠? 자료구조라면 이렇게 중간에 추가도 가능해야 합니다.
잘 보면 7은 11을 기준으로 뒤에 추가한 것이고, 5를 기준으로는 앞에 추가한 것입니다.
이번엔 반대로 해보았습니다.
아래에는 있던 7이 없어졌네요. 자료구조는 중간값을 삭제할 수도 있어야 합니다.
이 역시 11을 기준으로 뒤의 노드를 삭제한 것이고, 5를 기준으로는 앞의 노드를 삭제한 셈입니다.
정리하면
즉, 다음노드로 '갈수 있음' 상태는 한 방향으로 유지하되,
새로운 노드의 추가는 임의 노드를 기준으로 앞, 뒤에 넣거나 뺄 수 있어야 합니다.
(임의 노드가 맨 앞이나 맨 끝의 노드라 하더라도 말이죠.)
그러면 이제 좀 복잡해지죠? 전체 코드는 아래와 같습니다.
하나하나 보겠습니다. 우선 Node는 위에 작성한 코드와 똑같고, Single_List가 전체 단순연결리스트의 '객체'가 됩니다.
size와 is_empty 메서드는 말 그대로 리스트 안에 노드가 몇 개 인지, 노드가 아예 없는지 만을 확인하고자 만든 메서드 입니다.
그 다음부터가 추가 함수 2개, 삭제 함수 2개가 구현된 것입니다.
1. 대상 노드 앞에 새 노드 추가하기
먼저 value라는 값을 대상노드(여기서 대상노드는 self.head 입니다.) 앞에 넣고자 합니다.
리스트 안에 아무 데이터가 없으면 곧바로 self.head에 value를 가진 노드를 이어주면 됩니다. 이 코드가 if부분입니다.
리스트 안에 데이터가 이미 있으면, value를 넣은 노드를 새롭게 만든 후에 새롭게 self.head로 정의합니다. 이때 주의할 부분은 새롭게 만든 노드 뒤에 기존 노드인 self.head가 들어가는 부분입니다.
그리고 노드가 새롭게 들어갔으니 self.size 라는 값을 +1 해 주는 것입니다.
2. 대상노드 뒤에 새 노드 추가하기
앞에 넣는 것은 확인 했으니, 뒤에 넣는 것도 비슷할거라 생각이 되시죠?
여기서 기준 노드는 node라고 들어오는 전달인자 입니다.
즉, 기준노드의 next에 value값을 데이터로 가지는 새 노드를 만든 후에 연결하는 것입니다.
만일 이 기준 노드의 next에 또 다른 노드가 이미 연결되어 있다면, 이 연결을 새 노드를 만들 때 node.next라는 값으로 연결해 줍니다.
노드가 하나 추가 되었으니 size는 당연히 +1이 되겠죠.
3. 대상 노드 앞에있는 노드 삭제하기
이쯤 되면 눈치를 채셨으리라 봅니다. 리스트 자료구조에서 중요한 포인트는 '어느 지점'을 가르키는지와, '어느 지점'을 추가 혹은 삭제하는 '방법'이 중요합니다.
삭제에서는 해당 node를 그냥 무시하는 방법으로 처리합니다.
if문은 데이터가 없는 경우에는 삭제할 수 없기 때문에 print문만 넣어놓았습니다.
삭제할 대상이 있다면, self.head(삭제 대상 노드)의 next에 있는 노드를 self.head로 새롭게 갱신합니다.
즉, 기존 self.head에 있던 노드는 무시되는 것입니다.
노드가 하나 지워졌으니 전체 리스트 길이는 -1을 해줍니다.
4. 대상 노드 뒤에있는 노드 삭제하기
뒤에 있는 경우 삭제는 조금 복잡합니다. (뭐 그래도 아주 조금입니다)
삭제 대상 노드 뒤에 연결되어 있는 노드를 tmp로 담습니다. 그리고, tmp의 next로 이어진 다음 노드를 대상 노드 다음에 곧바로 붙입니다. 그러면 삭제를 원하는 노드는 자동으로 아무 관련이 없어집니다.
그러면 코드를 확인 해 보겠습니다.
먼저 insert_front는 잘 들어가집니다. 1 앞에 22를 넣었더니 22가 1 앞에 있는 것을 확인할 수 있습니다.
위 코드에 이어서 곧바로 맨 앞의 22를 삭제해보았습니다.
다시 head 값으로 1이 있는 것을 볼 수 있습니다.
'자료구조' 카테고리의 다른 글
| [Trie] 문자열 검색이 용이하게 만든 트리 (0) | 2022.07.06 |
|---|---|
| 스택과 데크(deque) (0) | 2022.06.03 |
| 연결리스트 - 이중 연결 리스트 (0) | 2022.05.26 |