본문 바로가기
TIL/Data Structures and Algorithms

(자료구조) 링크드리스트 (Linked List)

parksisi 2021. 1. 15. 10:03

1. 링크드리스트란

- 일반적인 배열이 순차적으로 연결된 공간에 데이터를 나열하는 구조라면, 링크드 리스트(혹은 연결 리스트)는 떨어진 곳에 존재하는 데이터를 포인터로 연결하여 관리하는 데이터 구조이다. 

- 사용자가 어떤 애플리케이션에서 배열을 사용 중이라면 아마 배열 대신 링크드 리스트를 쓰고 있을 가능성이 크다.

 

기본구조는 아래와 같다. 

- Node : 데이터 저장 단위. 실제 데이터값과 포인터로 구성되어있다. 아래 그림 왼쪽이 데이터값, 오른쪽이 포인터이다.

- Pointer : 각 노드 안에서 다음이나 이전 노드와의 연결 정보를 가지고 있는 공간이다. 아래 그림에서는 다음 노드의 정보만 들어가나 만약 이전, 다음 노드정보가 들어간다면 이를 더블링크드리스트라 부른다.

 

링크드리스트의 구조 (출처: https://en.wikipedia.org/wiki/Linked_list)

 

1. 아래는 파이썬으로 구현한 링크드리스트 코드이다.

 

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
    
class NodeMgmt:
    def __init__(self, data):
        self.head = Node(data)
        
    def add(self, data):
        if self.head == '':
            self.head = Node(data)
        else:
            node = self.head
            while node.next:
                node = node.next
            node.next = Node(data)
        
    def desc(self):
        node = self.head
        while node:
            print (node.data)
            node = node.next

 

2. 링크드리스트의 장단점은 아래와 같다.

  • 장점
    • 데이터 공간을 미리 할당하지 않아도 된다. 
  • 단점
    • 연결을 위한 별도의 데이터공간(포인터)가 필요하므로 메모리 공간 효율이 낮다.
    • 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느리다.
    • 중간 데이터 삭제시 앞뒤 데이터 연결을 재구성해야하는 부가적인 잡업이 필요하다.

 

3. 링크드 리스트의 복잡한 기능1 (링크드 리스트 데이터 사이에 데이터를 추가)

 

node3 = Node(1.5)

node = head
search = True
while search:
    if node.data == 1:
        search = False
    else:
        node = node.next

node_next = node.next
node.next = node3
node3.next = node_next

 

4. 링크드 리스트의 복잡한 기능2 (특정 노드를 삭제)

 

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
    
class NodeMgmt:
    def __init__(self, data):
        self.head = Node(data)
        
    def add(self, data):
        if self.head == '':
            self.head = Node(data)
        else:
            node = self.head
            while node.next:
                node = node.next
            node.next = Node(data)
        
    def desc(self):
        node = self.head
        while node:
            print (node.data)
            node = node.next
    
    def delete(self, data):
        if self.head == '':
            print ("해당 값을 가진 노드가 없습니다.")
            return
        
        if self.head.data == data:
            temp = self.head
            self.head = self.head.next
            del temp
        else:
            node = self.head
            while node.next:
                if node.next.data == data:
                    temp = node.next
                    node.next = node.next.next
                    del temp
                    return
                else:
                    node = node.next

 

# 추가 : 루비코드

 

1. node class

# linked_list.rb

class Node
	attr_accessor :data, :next_node

	def initialize(data)
		@data = data
	end
end

class LinkedList    #first node를 세팅해주는 클래스
	attr_accessor :first_node

	def initialize(first_node)
		@first_node = first_node
	end
end

node1 = Node.new("once")
node2 = Node.new("upon")
node1.next_node = node2
node3 = Node.new("a")
node2.next_node = node3
node4 = Node.new("time")
node3.next_node = node4

list = LinkedList.new(node1)

 

2. 읽기

- 배열의 시간복잡도는 0(1) 이지만, 링크드 리스트의 시간복잡도는 O(N)이다. 예를 들어 프로그램이 링크드 리스트의 인덱스 2에 있는 값을 읽을때 컴퓨터는 메모리 어디에서 찾아야 할지 바로 알 수 없으므로 인덱스 0부터 시작하여 찾아나가야 한다. 

 

class Node
	attr_accessor :data, :next_node

	def initialize(data)
		@data = data
	end
end

class LinkedList
	attr_accessor :first_node

	def initialize(first_node)
		@first_node = first_node
	end

	def read(index)
		# 리스트의 첫번째 노드에서 시작한다
		current_node = @first_node
		current_index = 0

		while current_index < index 
			current_node = current_node.next_node
			current_index += 1

			# 리스트의 끝에 도착했다면 찾고 있는 인덱스가 리스트에 없다는 뜻이므로 nil을 반환
			return nil unless current_node
		end

		return current_node.data
	end
end

node1 = Node.new("once")
node2 = Node.new("upon")
node1.next_node = node2
node3 = Node.new("a")
node2.next_node = node3
node4 = Node.new("time")
node3.next_node = node4

list = LinkedList.new(node1)

p list.read(3) # 결과 : "time"
p list.read(4) # 결과 : nil

 

3. 검색

 - 여기서의 검색은 리스트 내에서 어떤 데이터를 찾고 그 인덱스를 반환하는 것이다. 배열과 링크드리스트의 검색 효율성은 같다. 시간복잡도는 O(N)이다.

 

class Node
	attr_accessor :data, :next_node

	def initialize(data)
		@data = data
	end
end

class LinkedList
	attr_accessor :first_node

	def initialize(first_node)
		@first_node = first_node
	end

	... 중략

	def index_of(value)
		# 리스트의 첫 번째 노드에서 시작한다
		current_node = @first_node
		current_index = 0

		begin 
			if current_node.data == value
				return current_index
			end

			current_node = current_node.next_node
			current_index += 1
		end while current_node

		# 데이터 찾지 못한 채 전체 리스트를 순회했으면 nil을 반환한다.
		return nil
	end
end

node1 = Node.new("once")
node2 = Node.new("upon")
node1.next_node = node2
node3 = Node.new("a")
node2.next_node = node3
node4 = Node.new("time")
node3.next_node = node4

list = LinkedList.new(node1)

p list.index_of("time") # 결과인덱스 : 3

 

4. 삽입

 

시나리오 배열 링크드 리스트
맨 앞에 삽입 시간복잡도 0(N), 최악의 경우 시간복잡도 O(1), 최선의 경우
중간에 삽입 평균적인 경우 평균적인 경우
맨 끝에 삽입 시간복잡도 O(1), 최선의 경우 시간복잡도 O(N), 최악의 경우

링크드 리스트의 경우 중간 혹은 맨 끝에 삽입할 경우 맨 처음부터 시작하여 찾아나가기 때문에 시간복잡도가 O(N)만큼 걸리게 된다.

 

	def insert_at_index(index, value)
		current_node = @first_node
		current_index = 0

		# 먼저 삽입하려는 새 노드의 바로 앞 인덱스를 찾는다.
		while current_index < index
			current_node = current_node.next_node
			current_index += 1
		end

		# 새 노드를 생성한다
		new_node = Node.new(value)
		new_node.next_node = current_node.next_node

		# 새 노드를 가리키도록 앞 노드의 포인터를 수정
		current_node.next_node = new_node
	end

 

5. 삭제

시나리오 배열 링크드 리스트
앞에서 삭제 최악의 경우 최선의 경우
중간에서 삭제 평균적인 경우 평균적인 경우
끝에서 삭제 최선의 경우 최악의 경우

- 맨 앞 노드를 삭제할 경우 간단히 first_node가 두번째 노드를 가리키게 하면 된다.

- 마지막 노드 삭제의 경우 끝에서 두번째 노드를 가져와 포인터를 null로 바꿔주면 된다. 하지만 끝에서 두번째 노드를 가져오기 위해 리스트 앞에서부터 끝가지 링크를 따라가야 하므로 O(N)의 시간복잡도가 걸린다. 

 

def delete_at_index(index)
  current_node = @first_node
  current_index = 0

  # 먼저 삭제하려는 노드의 바로 앞 인덱스를 찾아 current_node에 할당한다
  while current_index < index - 1
    current_node = current_node.next_node
    current_index += 1
  end

  # 삭제하려는 노드의 바로 뒤 노드를 찾는다
  node_after_deleted_node = current_node].next_node.next_node

  # current_node의 포인터가 node_after_deleted_node를 가리키도록 수정
  # 이렇게 하면 삭제하려는 노드가 리스트에서 제외된다.
  current_node.next_node = node_after_deleted_node
end

 

 

6. 배열과 링크드 리스트의 시간복잡도 정리

 

연산 배열 링크드 리스트
읽기 O(1) O(N)
검색 O(N) O(N)
삽입 O(N) (끝에서하면 O(1)) O(N) (앞에서하면 O(1))
삭제 O(N) (끝에서하면 O(1)) O(N) (앞에서하면 O(1))

 

7. 링크드 리스트의 활용

- 링크드 리스트가 빛을 발하는 경우는 한 리스트를 검사해서 많은 원소를 삭제할 때다.

- ex) 이메일 주소 리스트 검토해서 유효하지 않은 형식의 이메일 모두 삭제하는 시스템

- 배열에서는 이메일 주소 삭제할 때마다 빈 공간 메꿔주는 추가 작업이 필요하다. 이 역시 O(N) 시간복잡도가 걸린다. 

- 반면 링크드 리스트의 경우 삭제 시 노드 연결해주는 작업 한번만 더 해주면 되기에 배열보다 더 효율적이다.

 

 

8. 더블 링크드 리스트

- 다음 데이터 주소 뿐만 아니라 이전 데이터 주소도 갖는다. 

- 만약 1만개의 노드가 있는 링크드 리스트에서 8천번째 있는 데이터 검색하려면 8천번의 서치 작업이 필요하다. 만약 이전 데이터 주소값을 가지고 있다면, 뒤에서 부터 약 2천번의 서치 작업만 거치면 원하는 값을 찾을 수 있다.

 

 

 

** 패스트캠퍼스의 '알고리즘/기술면접 완전 정복 올인원 패키지' 강의를 듣고 작성한 글입니다

'TIL > Data Structures and Algorithms' 카테고리의 다른 글

공간복잡도  (0) 2021.01.26
(자료구조) 힙  (0) 2021.01.26
(자료구조) 트리구조 (Tree)  (0) 2021.01.26
(자료구조) 해쉬테이블  (0) 2021.01.22
알고리즘 복잡도  (0) 2021.01.22

'TIL/Data Structures and Algorithms' Related Articles

티스토리툴바