[알고리즘] 패스트캠퍼스 챌린지 04일차

[알고리즘] 패스트캠퍼스 챌린지 04일차

링크드리스트(= 연결 리스트; Linked List)

배열은 미리 공간을 확보해놓고 데이터를 넣는 방식, 링크드 리스트는 필요할 때마다 데이터를 추가할 수 있는 구조 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조

배열은 데이터만 저장, 링크드 리스트는 (그 데이터 + 다음 데이터를 가르키는 주소)를 저장한다.

노드(Node): 데이터 저장 단위 (데이터값, 포인터) 로 구성 포인터(pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간 ( 주소 )

링크드리스트에서 첫번째 노드만 알고 있으면 연결된 모든 노드를 찾아갈 수 있음.

첫번째 노드에서 다음 데이터의 주소로 다음 데이터를 찾음

계속 찾아나감

포인터가 null이면 마지막 데이터!

파이썬에서 링크드리스트 구현

(데이터, 포인터)를 저장하기 위해 노드 Class를 만들어준다.

// 포인터를 next에 넣어준다 // 다음 노드 데이터의 주소가 없으면 None(마지막 노드!) class Node: def __init__(self, data, next=None): self.data = data self.next = next // 첫번째 노드 node1 = Node(1) // 두번째 노드 node2 = Node(2) // node1 다음 노드가 node2임 node1.next = node2 // 첫번째 노드가 node1임을 head 변수를 통해 저장 head = node1

데이터를 추가하는 과정을 이쁘게 함수로 만들면 아래처럼 되겠다.

def add(data): node = head // 그 노드에 다음 노드를 가르키는 주소가 있으면 다음 노드를 찾아감(반복) while node.next: node = node.next // 다음 노드를 가르키는 주소가 없으면 여기로!! node.next = Node(data)

LinkedList, Node 추가하는 함수까지 Swift로 만들어도 봤다.

이렇게 노드를 만들고

class Node { var data: DataType? var next: Node? init(_ data: DataType, next: Node? = nil) { self.data = data self.next = next } }

이렇게 직접 노드 하나하나 만들어서 하나씩 출력해보기도 성공

let node1 = Node(1) let node2 = Node(2) node1.next = node2 head = node1 var currentNode = node1 while currentNode.next != nil { print(currentNode.data) currentNode = currentNode.next! } print(currentNode.data)

10개 노드를 순서대로 추가하고 프린트 하는 것도 Swift로 테스트 완료!

var head: Node? var node: Node? func add(data: Int) { node = head while node?.next != nil { node = node?.next } node?.next = Node(data) } let firstNode = Node(1) head = firstNode for index in 2...10 { add(data: index) } var currentNode = firstNode while currentNode.next != nil { print(currentNode.data) currentNode = currentNode.next! } print(currentNode.data)

LinkedList에 add 하는 것만 해봤지만, remove, 중간에 insert 등등 기능들 다 함수로 만들고, LinkedList 클래스를 만들어서 관리하면 될 것 같다.

마지막 테스트하는데 계속 안되서 헤매다가 겨우 해결했다ㅠㅠ 조금 복잡했던 오늘 수업..! ㅎ...

오늘의 강의 인증샷! ㅎㅎ

https://bit.ly/37BpXiC

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.

from http://tnqtnq.tistory.com/81 by ccl(A) rewrite - 2021-09-09 13:00:41