[SW Intermediate] Linked List

 연결 리스트(Linked List)

---

리스트(List)

1) 동적 배열로 작성된 순차 리스트

2) 자료의 삽입, 삭제 연산

- 원소의 이동 작업이 필요하다.

3) 원소의 개수가 많고 삽입, 삭제 연산이 빈번한 작업

- 소요되는 시간이 크게 증가

---

리스트 복사

# 1.
new_list = old_list

주소의 복사, 얕은 복사

 

# 2.
new_list = old_list[:]

슬라이싱(slicing), 깊은 복사

 

# 3.
new_list = []
new_list.extend(old_list)

✔ extend(): 리스트를 추가하는 함수

깊은 복사

 

# 4. 
new_list = list(old_list)

✔ list() 

깊은 복사

 

# 5.
import copy
new_lsit = copy.copy(old_list)

copy 활용, 깊은 복사

 

# 6.
new_list = [i for i in old_list]

리스트 함축, 깊은 복사

 

# 7.
import copy
new_list = copy.deepcopy(old_list)

리스트 원소 까지도 깊은 복사, 가장 느림

 

---

연결 리스트(Linked List)

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

 

1) 자료의 논리적인 순서와 메모리 상의 물리적인 순서가 일치하지 않고,

개별적으로 위치하고 있는 원소의 주소를 연결하여 하나의 전체적인 자료구조를 이룬다.

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

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

4) 탐색 - 순차 탐색

5) 연결리스트 구조

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

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

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

- 헤드: 리스트의 처음 노드를 가리키는 레퍼런스

 

 

 

---

연결 리스트 주요 함수

1) add_to_first(): 연결리스트 앞쪽에 원소를 추가하는 연산

2) add_to_last(): 연결리스트 뒤쪽에 원소를 추가하는 연산

3) add(): 연결리스트의 특정 위치에 원소를 추가하는 연산

4) delete(): 연결리스트의 특정 위치에 있는 원소를 삭제하는 연산

5) get(): 연결리스트의 특정 위치에 있는 원소를 리턴하는 연산

 

'''
단순 연결 리스트

1) 노드가 하나의 링크 필드에 의해 다음 노드와 연결되는 구조를 가짐
2) 헤드가 가장 앞으 노드를 가리키고, 각 노드의 링크 필드가 연속적으로
다음 노드를 가리킴
3) 최종적으로 None 을 가리키는 노드가 리스트의 마지막 노드이다.

'''

# 삽입 연산

def addtoFirst(data) # 첫 노드에 데이터 삽입
    global Head
    Head = Node(data, Head) # 새로운 노드 생성

# 특정 위치에 삽입하는 연산

def add(pre, data) # pre 다음에 데이터 삽입
    if pre == None:
        print('error')
    else:
        pre.link = Node(data,pre.link)

# 마지막 노드로 데이터 삽입
def addtoLast(data) # 마지막에 데이터 삽입
    global Head
    if Head == None: # 빈 리스트 이면
        Head = Node(data, None)
    else:
        p = Head
        while p.link != None # 마지막 노드 찾을 때 까지
            p = p.link
        p.link = Node(data,None)

# 삭제연산
def deletetoFirst(): # 처음 노드 삭제
    global Head
    if Head == None:
        print('error')
    else:
        Head = Head.link

# 특정 위치의 노드 삭제
def delete(pre): # pre 다음 노드 삭제
    if pre == None or pre.link == None:
        print('error')
    else:
        pre.link = pre.link.link

 

 

---

이중 연결 리스트

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

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