Linked List

List 

1. 순서를 가진 데이터의 묶음 - 같은 데이터의 중복 저장 가능

2. 시퀀스 자료형 - 인덱싱, 슬라이싱, 연산자, 메서드 사용 가능

3. 크기제한 없음, 타입제한 없음

 

 

	크기	데이터의 타입
배열	변경 불가	선언된 한가지 타입만 저장가능
리스트	변경 가능	다양한 데이터 타입 저장가능

순차 리스트 : 배열을 기반으로 구현된 리스트

연결 리스트 : 메모리의 동적할당을 기반으로 구현된 리스트

 

파이썬의 리스트는 동적 배열로 작성된 순차 리스트. 원소의 개수가 많고 삽입/삭제 연산이 빈번한 작업은 소요되는 시간이 크게 증가

 

리스트 복사 (아래로 갈수록 수행시간이 길다)

	코드	설명
1	new_list=old_list	주소의 복사, 얕은 복사
2	new_list=old_list[:]	슬라이싱, 깊은 복사
3	new_list=[] new_list.extend(old_list)	extend() : 리스트를 추가하는 함수 깊은 복사
4	new_list=list(old_list)	list(), 깊은 복사
5	import copy new_list=copy.copy(old_list)	copy 활용, 깊은복사
6	new_list=[i for i in old_list]	리스트함축, 깊은 복사
7	import copy new_list=copy.deepcopy(old_list)	리스트 원소까지도 깊은 복사 가장 느림

'깊은 복사'는 원본 리스트의 객체까지 복사를 의미

 

연결 리스트

값을 찾을 때 시간복잡도는 O(n)

리스트의 단점을 보완한 자료 구조

1. 자료의 논리적인 순서와 메모리 상의 물리적인 순서가 일치하지 않고, 개별적으로 위치하고 있는 원소의 주소를 연결하여 하나의 전체적인 자료구조

2. 링크를 통해 원소에 접근하므로, 순차 리스트에서 물리적인 순서를 맞추기 위한 작업이 필요하지 않음

3. 자료구조의 크기를 동적으로 조정할 수 있어, 메모리의 효율적인 사용이 가능

4. 탐색 - 순차탐색

 

연결 리스트 사용을 위한 주요 함수

함수명	기능
addtoFirst()	연결 리스트의 앞쪽에 원소를 추가
addtoLast()	연결 리스트의 뒤쪽에 원소를 추가
add()	연결 리스트의 특정 위치에 원소를 추가
delete()	연결 리스트의 특정 위치에 있는 원소를 삭제
get()	연결 리스트의 특정 위치에 있는 원소를 리턴

 

노드 : 연결 리스트에서 하나의 원소에 필요한 데이터를 갖고 있는 자료단위

데이터 필드 : 원소의 값을 저장하는 자료구조

링크 필드 : 다음 노드의 주소를 저장하는 자료구조

헤드 : 리스트의 처음 노드를 가리키는 레퍼런스로 데이터를 가지고 있지 않음

 

단순 연결 리스트

- 노드가 하나의 링크 필드에 의해 다음 노드와 연결되는 구조

- 헤드가 가장 앞의 노드를 가리키고, 각 노드의 링크 필드가 연속적으로 다음 노드를 가리킴

- 최종적으로 None을 가리키는 노드가 리스트의 가장 마지막 노드

 

push/pop 연산의 알고리즘

def push(i)   # 원소 i를 스택 top(맨앞) 위치에 push
  global top
  top=Node(i, top)  # 새로운 노드 생성

def pop() :   # 스택의 top을 pop
  global top

  if top == None :  # 빈 리스트이면
    print("error")
  else:
    data=top.data
    top=top.link    # top이 가리키는 노드를 바꿈
    return data

 

이중 연결 리스트(Doubly Linked List)

- 양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트

- 두 개의 링크 필드와 한 개의 데이터 필드로 구성

- 저장 공간이 더 필요하다는 단점

 

 

 참고 👉 SW expert academy