연결리스트 (3) 썸네일형 리스트형 [자료구조] 연결리스트-3 (양방향 연결 리스트) 2021.07.12 - [자료구조] - [자료구조] 연결 리스트-1 2021.07.12 - [자료구조] - [자료구조] 연결리스트-2 (추가/삭제)- 에 이은 내용 이전 포스팅의 Remove에서 마지막 노드를 삭제하기 위해 head부터 마지막 노드까지 순차적으로 이동했다. 나중에 정리하겠지만, 이렇게 삭제를 하게 될 경우 remove시도 시 데이터의 갯수만큼 시간복잡도가 증가하기 때문에 빅오 표기법으로 O(n)의 시간복잡도를 갖게 되는 최악의 알고리즘이 된다. 이를 피하기 위해서 검색알고리즘을 사용하는데 지금 우리는 알고리즘을 추가하여 시간복잡도를 줄이기 보다, Head와 마찬가지로 Tail이라는 마지막 노드를 가리키는 변수를 추가하여 마지막 노드를 삭제해보려 한다. 이때 양방향 연결리스트에 대해서 함께.. [자료구조] 연결리스트-2 (추가/삭제) 2021.07.12 - [자료구조] - [자료구조] 연결 리스트-1 에 이은 내용 앞선 포스팅에서 노드를 구성했다면 이번 포스팅에선 노드를 관리하고 추가/삭제가 용이한 연결리스트 클래스를 만들것이다. 노드클래스가 준비되었으니 바로 시작하자. LinkedList클래스를 생성하면 head라는 속성을 추가해준다. 변수명은 조금 달라도 되지만 보통 첫번째 노드를 가리키는 명칭이면 된다. head에는 LinkedList의 첫번째(0번째) 노드를 할당하자. 1. Append class LinkedList { var head: Node? func append(value: Int) { let newNode = Node(data: value) if head == nil { head = newNode } else { va.. [자료구조] 연결 리스트-1 자료구조의 리스트는 순차리스트(배열)과 연결리스트(Linked List)로 나뉜다. 연결리스트는 순차리스트와 달리 삽입/삭제 등 변화에 더욱 편리한 자료구조인데, 이러한 강점은 연결리스트의 각 요소가 어떻게 구성되는지 알면 이해가 된다. 연결리스트의 각 요소를 Node(이하 노드)라고 하는데, 노드는 정보를 담는 데이터와 연결된 다른 노드의 주소(포인터)를 담는다. 그림으로 표현한다면 아래와 같다. Data와 Next Address를 묶어서 하나의 노드라고 한다. Next Address는 위에서 말한 다음 노드의 주소를 담고있다. 언어에 따라서 NextAddress에 타입은 적절한 형태로 바뀔 수 있겠지만 보통의 경우 NextAddress에 할당되는것은 다음으로 연결되어야 할 노드의 주소가 된다. 노드 .. 이전 1 다음
