Swift - Data Structure[LinkedList]

짠승이·2022년 1월 6일

코딩테스트를 위한 공부!

오늘의 포스팅 주제!

🛠LinkedList🛠

일단 LinkedList를 알아보기전! DataStructure를 먼저 짚고 넘어가야될것 같습니다.
DataStructure == "자료구조" 가! 되겠습니다!
LinkedList 는 데이터를 표현하는 하는 자료구조중 하나 입니다.

LinkedList는 배열과 흡사한 성격을 가지고 있어요 .
일단 배열을 먼저 살펴보면

⭐️ 배열[Array]

배열은 쉽게 말해 하나의 박스안에 Index 를 부여 받고
하나의 박스안에 나란히 줄서 있는것을 배열이라고 합니다 .

배열은 이 처럼 하나의 배열로써 자리매김 합니다.

또한 배열에 들어간 순서대로 Index번호를 부여받게 되지요
하지만 만약 Index가 아닌 (즉 총 배열의 Range가 줄어듬)이 아닌
element(요소)를 삭제(delete) , 삽입(Insert) 하게 될경우

이런식으로 배열의 요소를 재배치 하는 과정에서 오버헤드 가 발생하게 됩니다 .

이를 방지하고 기존 배열의 단점을 보완하여 사용되는 것이
LinkedList 입니다.

🛠LinkedList -개념-

LinkedList는 말그대로 배열의 요소들을 하나의 공간에 묶어 보관하는것이 아닌
Link(연결) 하여 보관 하는 것입니다.
조금더 알기 쉽게 그림으로 보자면!

LinkedList는 서로 다른 요소들로 구성된 -linear data structure- ( 선형데이터구조)입니다.
또한 LinkedList의 첫번째 요소를 Head(머리) 라고 하고
요소를 가리키는 Reference가 없는 요소를 Tail(꼬리) 이라고 합니다.

이렇게 Node(요소) 와 Reference(참조)를 통하여 데이터를 보관하는 LinkedList는
메모리의 공간을 보다 더 효율적으로 사용할수있습니당.

그리고 Delete Insert 등에서 벌어질수 있는 이슈들을 방지할수도 있지욘!!
하지만 배열처럼 Index로 요소에 접근할순 없습니다 Index가 없기때문에요
그래서 데이터에 접근할시 첫번째요소 (Head)부터 마지막요소(Tail)까지 순차적으로 접근해야합니다.

그럼 Node를 만들어 조금더 개념이해를 해보겠습니다!

🛠Node

플레이 그라운드 입니다.
주석을 잘봐주시길 바래용

위에서 설명드린대로 List의 첫요소 Head는 node1이라고 볼수 있습니다 .
next를 통하여 이어져 있기 때문에 첫시작이 node1이기 때문이쥬
그렇다면 next(Reference) 를 가지고 있지 않는 node3은 Tail 이 되겠지용?
가장 밑 콘솔로그와 오른쪽에 진행순서에 따라 OutPut되어 나오는 데이터를 잘봐주시게 되면
조금더 이해가 빠르실꺼라 생각합니다.

next : 다음 Node의 Reference를 추적합니다.

🛠LinkedList

링크 리스트(LinkedList) 는 모든 Node를 보유할수있는 Struct(구조체) 입니다.
head와 tail을 포함하고 Bool을 통하여 Node 내의 Empty를 체크할수 있어야합니다 ..

⚙️ Operation

LinkedList에 Data를 삽입하는 방법은 여러가지가 있습니다.
그중 Push 에 대해 설명하겠습니다 .

👉🏻Push

Push 는 말그대로 List안으로 Data를 밀어넣습니다.
이때 그냥 밀어넣는것이 아닌 Head의 위치로 밀어넣습니다
그림으로 설명해드리겠습니다.

이러한 리스트가 있다는 가정하에
현재 Head의 Node는 빨간색입니다.
하지만 여기서
만약 노란색 원을 Push 하게 된다면 ?

Head의 Node는 노란원으로 대체 됩니다.
그리고 Reference는 다음 Node로 빨간원을 가리키게 되지요
자 그럼 LinkedList에 Push method를 구현해보겠습니다.

그럼 인스턴스를 생성한뒤 출력해보겠습니다 .
일단 출력을 좀더 보기좋게 하기위해 CustomStringConvertible 를 통해 조금 손을 보겠습니다.

이후 인스턴스 생성 , push ,출력

인스턴스를 생성합니다. Head가 없기 때문에 "Empty List"가 print 되는게 보이시죠?
처음 2가 push 되었을때 tail이 없어 2가 head가 됩니다.
자 그후 push를 이용해서 여러 값들을 대입을 했습니다.
처음 Node를 만들고 next를 통하여 연결했을때와 다르게
값들이 앞으로 추가 되는게 보이실겁니다.이게 push의 기능이지요
결국 마지막에 push된 54가 head의 자리에 있습니다.

Append👈

데이터 삽입의 다른 방법인 Append를 알아보겠슴당.

Append는 Tail은 자신이 가지고있는 Reference 에 삽입 하려는 Node를 가리키게 합니다.
그후 삽입되는 Node의 Reference는 어떤한 Node도 가리키지 않습니다.
기존 꼬리 Node가 변경되는 것입니다.

코드를 살펴보면
LinkedList에 추가하는 method 입니다.

출력문을 보게 되면 Head가 아닌 Tail이 바뀌는 것을 볼수 있습니다.

Insert👇

insert는 원하는 자리에 Node를 삽입하는 방법입니다.
하지만 LinkedList는 index가 없기 때문에 접근하기 위해선
삽입하려는 데이터가 어떤 데이터 뒤에 삽입될것인지를 정해주면 됩니다.

여기선 검은색 원을 가리키는 Referece를 노란색원으로 바꿔주는 것입니다 .

특정 node를 생성하고 node 에게 insert를 위한 index를 부여하는 함수 입니다.
LinkedList는 배열처럼 index를 가지고 있지 않기에 index를 만들어 할당 해주어야 합니다.
배열의 index는 0 부터 시작 되고 이를 LinkedList에 적용하기 위해
currentIndex와 현재의 Node를 할당해야합니다.
그리고 현재 Node가 nil 이 아니고 할당될 index보다 currentIndex가 작으면 while루프가 시작됩니다.
루프가 실행되면 지금 현재 CurrentNode는 자신의 다음 Node의 값이 제공됩니다.
또한 현재의 Index또한 1 씩 증가 되야 합니다 .
그리고 조건이 맞지 않아 while에서 빠져 나오게 되면
빠져나왔을때의 Node를 반환합니다.

func insert는 삽입할 데이터와 Node(index를 부여받은 Node)를 매개변수로 받아
Node에 다음 Node를 변경하는 것입니다 .

출력