링크드리스트 | 파이썬 | 발전을 위한 기초

왜 우리가 이것을 배워야 합니까?

우리 모두는 데이터 구조와 알고리즘이 훌륭한 소프트웨어 엔지니어가 되기 위한 기초라는 것을 알고 있습니다.

일반적으로 이러한 기본 개념은 대학에 재학 중이거나 대기업 인터뷰를 준비하는 경우에만 가치 있는 것으로 간주됩니다.

그러나 나는 이것에 대해 다른 견해를 가지고 있습니다. 엔지니어로서 스스로에게 다음과 같은 질문을 던져야 합니다. "엔지니어로서 X를 알아야 합니까?"대답이 '예'인 경우 일반적으로 좋은 엔지니어가 되기 위해 해당 주제에 시간을 할애하십시오.

따라서 질문은 엔지니어로서 Linked-List라는 가장 기본적이지만 유용한 데이터 구조를 알아야 한다고 생각하십니까?

나는 큰 예를 들었다!!

시작하겠습니다.

정의와 사전

연결된 목록은 선형 데이터 구조입니다.

기본적으로 data 및 next 두 가지만 포함합니다.

이 data는 int에서 배열 또는 사전에 이르기까지 무엇이든 될 수 있습니다.

next는 다음Node을 가리키는 포인터입니다.

Node는 연결된 목록의 모든 연결 엔터티에 사용하는 이름일 뿐입니다. 노드는 인덱스로 배열에 있는 것과 다소 유사합니다.

간단히 말해서 연결 리스트는 포인터로 함께 연결된 Nodes의 모음입니다.

이 데이터 구조가 존재하는 이유는 무엇입니까?

우리는 이미 arrays로 알려진 선형 데이터 구조를 가지고 있는데 왜 유사하지만 새로운 것을 만들었습니까? 왜요?

그럼 질문을 할게요:
배열 중간에 새 요소를 어떻게 추가합니까?

새 요소를 추가할 위치를 찾습니다.

새 요소 추가

나머지 배열을 1로 이동합니다

.

연결된 목록은 중간에 새 요소를 추가한 후 배열을 이동하는 것과 같은 문제를 해결합니다.

구현

파이썬에서는 아래 주어진 코드와 같이 이 데이터 구조를 반영하는 클래스를 만드는 것이 정말 쉽습니다.

class LinkedList:
    def __init__(self, head=None):
        self.head = None

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

배열에서 만들기

이 연결 목록을 어떻게 만들고 실제로 볼 수 있는지 궁금할 것입니다.
이를 위해 배열에서 연결된 목록을 만든 다음 다른 함수를 사용하여 연결 목록의 모든 노드를 방문하는 간단한 함수를 작성할 수 있습니다.

def createFromArray(nodeList):

    ll = LinkedList()

    prev = None
    for n in nums:
        curr = Node(n)

        if not prev:
            ll.head = curr
        else:
            prev.next = curr

        prev = curr

    return ll

# Make linked-list from array - O(n)
nums = [1,2,3,4,5]
ll = createFromArray(nums)

횡단

트래버스 또는 간단한 단어로 연결된 목록의 모든 노드를 방문하려면 다음과 같이 할 수 있습니다.

def traverseList(ll):
    curr = ll.head

    while curr:
        print(curr.data, end=" -> ")
        curr = curr.next

# traverse a linked-list O(n)
traverseList(ll)

이 기능이 마음에 들고 더 자세히 알고 싶다면 계속 따라오세요. 다음으로 연결된 목록에서 몇 가지 일반적인 작업에 대해 이야기하겠습니다.

즐거운 코딩하세요.

학점:

표지 사진 by Joey Kyber