Linked List

• Array

  • 개념

  • 장점

  • 단점

  • time complexity

• Linked List

  • 개념

  • 장점

  • 단점

  • time complexity

  • 코드 짜보기
    • 단일 연결 리스트

 

Array 

• 개념

가장 기본적인 자료구조.

논리적 저장 순서, 물리적 저장 순서가 일치한다.

 

• 장점

index로 해당 element에 접근할 수 있다. 찾고자하는 원소의 인덱스 값을 알고 있으면 N-1에 해당원소로 접근할 수 있다.

즉, Random access가 가능하다는 장점이 있는 것이다.

 

• 단점

삭제 또는 삽입의 과정에서 해당 원소에 접근하여 작업을 완료한 뒤,

또 한가지의 작업을 추가적으로 해줘야 하기 때문에, 시간이 더 걸린다.

 

만약 배열의 원소 중 어느 원소를 삭제했다고 했을 때, 배열의 연속적인 특징이 깨지게 된다. 즉 빈 공간이 생기는 것이다.

따라서 삭제한 원소보다 큰 인덱스를 갖는 원소들을 shift해줘야 하는 비용이 발생

• Time complexity

만약 배열의 원소 중 어느 원소를 삭제했다고 했을 때, 배열의 연속적인 특징이 깨지게 된다. 즉 빈 공간이 생기는 것이다.

따라서 삭제한 원소보다 큰 인덱스를 갖는 원소들을 shift해줘야 하는 비용이 발생

-> 이 경우 시간복잡도 O(n)이 된다.

 

그렇게 때문에 Array의 삭제 기능에 대한 time complexity의 worst case 는 O(n)이다.

 

만약 삽입한다면, 마찬가지로 모든 원소들의 index를 +1 shift해줘야 하므로 O(n).

 

 

Linked List

• 개념

단일 연결 리스트

 

Array의 단점을 해결해줄 수 있다.

Linked List에서 각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하고 있다.

따라서 이 부분만 다른 값으로 바꿔주면 삭제와 삽입을 O(1)만에 해결할 수 있다.

 

이 Linked List는 Tree의 근간이 되는 자료구조이며, Tree에서 그 유용성이 드러난다.

 

Linked List 종류

1. Single 단일 연결 리스트

( 각 노드에 자료공간과 한 개의 포인터 공간)

2. Double 이중 연결 리스트 

3. Circular 환형 연결 리스트

 

• 장점

  • list 의 길이를 동적으로 조절 가능
  • 데이터의 삽입과 삭제가 쉬움

Linked List에서 각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하고 있다.

따라서 이 부분만 다른 값으로 바꿔주면 삭제와 삽입을 O(1)만에 해결할 수 있다.

• 단점

  • 임의의 노드에 바로 접근 불가
  • 다음 노드위치 저장을 위한 추가 공간 필요
  • 거꾸로 탐색 어려움

원하는 위치에 삽입을 하고자 하면 원하는 위치를 Search과정에 있어서 처음부터 다 확인해봐야 한다는 것이다.

Array와는 달리 논리적 저장 순서와 물리적 저장 순서가 일치하지 않는다.

일단 삽입하고 정렬하는 것과 마찬가지.

 

• Time complexity

따라서 어떠한 원소를 삭제 또는 추가하고자 했을 때, 그 원소를 찾기 위해서 O(n)의 시간이 추가적으로 발생하게 된다.

Linked List 자료구조는 search에도 O(n)의 시간복잡도를 갖고,

삽입, 삭제에 대해서도 O(n)의 시간복잡도를 갖는다. 

 

• 코드 짜보기 (단일 연결 리스트 구현하기)

  • 삽입 / 삭제

삽입

삭제

•  

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



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

    def add(self,data):
            new_node = Node(data) 
            #새 data를 새로운 노드에 저장한다#만약 head data가 없으면. self.head가 0이면 
            if not self.head:
                
                self.head = new_node
            else:
                node = self.head
            #head가 없으면 head data를 node에 넣고
            while node.next:
                #노드뒤에 data값이 있으면  next값을 node에 넣는다
                node = node.next
            #newnode를 맨 뒤에 넣는다.
            node.next = new_node


    def delete(self, data):
        node = self.head
        #첫 데이터를 node로 지정
        if node.data == data:
        #data와 node와 같다면
            self.head = node.next
            #node의 값에 next를 넣는다
            del node

        else:
            while node.next:
                #
                next_node = node.next
                if next_node.data == data:
                    node.next = next_node.next_node
                    del next_node

                else:
                    node = node.next

    def find(self, data) :
        node = self.head
        while node:
            if node.data == data:
                return node
            else:
                node = node.next

    def print(self):
        node = self.head
        while node:
            print(node.data)
            node = node.next


ll = LinkedList()
ll.add(1)
ll.add(2)
ll.add(3)
ll.print()

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure 인용
https://daimhada.tistory.com/72?category=820522 인용