노드 : 연결 리스트에서 각각의 원소를 칭하는 말.
노드가 갖고 있는 것은 데이터와 뒤쪽 노드를 가리키는(참조하는) 포인터이다.
Head Node : 맨 앞에 있는 노드
Tail Node(꼬리 노드) : 맨 끝에 있는 노드
Prodecessor Node(앞쪽 노드) : 각 노드에서 바로 앞에 있는 노드
Successor Node(뒤쪽 노드) : 바로 뒤에 있는 노드
* 노드가 하나도 없는 빈 연결 리스트를 생성한다. head는 머리 노드에 대한 참조일 뿐 머리 노드 그 자체가 아니다. 노드가 존재하지 않는 빈 연결리스트는 head가 참조하는 곳이 없으므로 (=참조해야 하는 노드가 존재하지 않으므로) 그 값이 null.
- 가장 끝에(꼬리에) 삽입
1. 리스트가 비어 있을 때 : 맨 앞에 노드 삽입하는 것과 같은 처리
2. 리스트가 비어 있지 않을 때 : 리스트의 맨 끝에 노드 삽입. 가장 끝 노드, 즉 꼬리 노드를 찾는 과정을 수행해야함. ptr이 참조하는 곳을 그 뒤쪽 포인터로 업데이트 하는 과정을 반복함으로써 노드를 맨 앞부터 순서대로 스캔함. 삽입 후에 꼬리 노드를 참조한다.
- 검색 수행
(함수의)인수로 주어진 data와 값이 같은 노드를 검색한다. 이때는 선형 알고리즘을 사용. 즉 리스트 안의 노드를 맨 앞부터 순서대로 스캔한다.
*종료조건 1) 검색 조건을 만족하는 노드를 발견하지 못하고 tail node까지 왔을 경우
*종료조건 2) 검색 조건을 만족하는 노드를 발견한 경우
def search(self, data: Any) -> int:
""data와 값이 같은 노드 검색"
cnt = 0;
ptr = self.head;
whlie ptr is not null:
if ptr.data == data:
self.current = ptr;
return cnt;
cnt += 1;
ptr = ptr.next;
return -1;
스캔 중인 노드를 참조하기 위한 변수 ptr을 head로 초기화. 맨 앞의 노드를 A라고 가정. 이 과정을 통해서 ptr이 참조하는 곳은 head가 참조하는 head node A가 된다. (근데 여기서 궁금한 점!!! ptr이 참조하는 곳은 head / A 의 link or data? : LINK!!!! )
ptr값이 null이 아니면 검색할 data == ptr.data의 bool 값을 판단한다. T이면 성공임. 주목 포인터 변수 current 에 ptr 대입 후, 찾은 노드의 위치를 나타내는 cnt 업데이트 후 반환해준다.
ptr == ptr.data -> 다음 노드로 스캔 진행. ptr은 다음 노드를 참조하여 참조하고 있는 노드가 업데이트 된다.
return -1 #검색 실패함
- 머리에 노드 삽입
def add_first(self, data: Any) -> None:
""맨 앞에 노드 삽입""
ptr = self.head
self.head = self.current = Node(data,ptr)
삽입하기 전의 head node(A) 참조하는 포인터 변수를 ptr에 저장. Node(data,ptr)로 삽입할 노드를 생성한다. 삽입할 노드의 데이터는 data가 되고 뒤쪽 link 부분은 ptr(삽입하기 전의 노드 A)가 된다. 이때 대입을 통해서 head는 삽입한 노드를 참조하도록 업데이트.
- 꼬리에 노드 삽입
def add_last(self, data: Any):
""맨 끝에 노드 삽입""
if self.head is null:
self.add_first(data)
else:
ptr = self.head;
while ptr.next is not null:
ptr = ptr.next;
ptr.next = self.current = Node(data, None);
리스트가 비어있을 때는 맨 앞에 노드 삽입하는 것과 같고 그게 아닌 경우에는 ptr이 참조하는 곳을 그 뒤쪽 포인터로 계속 업데이트 하는 과정을 바복함으로써 노드를 맨 앞부터 순서대로 스캔한다. while문 종료될 때는 ptr.next가 참조하는 곳이 null값일 때. 즉 가장 끝자락으로 갔다는 ... 꼬리 부분에 삽입하기 때문에 삽입 노드를 link부분을 None(=null)으로 설정했다. 어떤 노드도 참조하지 않아야 하기 때문이다. 그리고 삽입 전 마지막 노드의 뒤쪽 포인터(link) ptr.next가 참조하는 곳이 새로 삽입한 노드가 되도록 업데이트 해야한다.
- 머리 노드(head node) 삭제
삭제 후에는 삭제하기 전에 머리 노드가 참조했던 노드를 참조한다.
*만약 리스트에 노드가 하나밖에 없다면?
삭제하기 전의 head node는 tail node이기 때문에 뒤쪽 포인터 head.next의 값은 null이다. 이 null을 head에 대입하면 결국 리스트는 빈 상태가 된다.
- 꼬리 노드(tail node) 삭제
def remove_last(self):
""꼬리 노드를 삭제""
if self.head is not null:
if self.head.next is null:
self.remove_first()
else:
ptr = self.head
pre = self.head
while ptr.next is not null:
pre = ptr;
ptr = ptr.next;
pre.next = null;
self.current = pre;
자바와 파이썬이 섞인..ㅋㅋ 형태의 간략한 코드.
ptr은 스캔 중인 노드의 head를 가리키고 pre는 스캔 중인 노드의 앞쪽 노드를 가리킨다. 다음 노드 값이 null이 아니라면 앞쪽 노드인 pre는 현재 스캔 중인 노드를, 현재 스캔 중인 노드는 다음 노드를 가리키게 한다.
while문을 종료할 때 ptr은 꼬리 노드를 참조하고, pre는 맨 끝에서 2번째 노드를 참조한다. 삭제 후, 맨 끝에서 2번째 노드의 뒤쪽 포인터에 null을 대입하므로 가장 끝에 있는 노드는 어디에도 참조되지 않는다. 따라서 주목 포인터 current가 참조하는 곳은 삭제한 뒤의 꼬리노드 pre로 업데이트 하는 과정 필요.
- 임의의 노드 삭제
def remove(self, p: Node) -> null:
""노드 p를 삭제""
if self.head is not null:
if p is self.head: #p가 head node이면
self.remove_first() #head node 삭제
else:
ptr = self.head;
whlie ptr.next is not p: #다음 노드가 self.head가 아닐 경우
ptr = ptr.next;
if ptr is null:
return;
ptr.next = p.next;
self.current = ptr;
self.no -= 1;
def remove_current_node(self) -> null:
""주목 노드 삭제""
self.remove(self.current);
def clear(self) -> null:
""전체 노드 삭제""
whlie self.head is not null:
self.remove_first();
self.current = null;
self.no = 0;
def next(self) -> bool:
""주목 노드를 한 칸 뒤로 이동""
if self.current is null or self.current.next is null:
return false;
self.current = self.current.next;
return True;
삭제할 노드 p의 앞쪽 노드를 찾는 과정을 수행한다. while 문은 head node에서 시작해서 스캔 중인 노드 ptr의 뒤쪽 포인터인 ptr.next가 p와 같아질 때까지 반복한다. null을 만나는 경우에는 p가 참조하는 노드가 존재하지 않는다는 뜻인데, return문으로 함수를 종료한다. 그러다 ptr.next가 p와 같아지면 whlie문을 종료하고 이때 ptr이 참조하는 곳은 삭제할 노드의 앞쪽(pre)노드가 된다.
삭제할 노드 p의 뒤쪽 포인터(link) p.next를 pre노드(p이전의 노드)의 뒤쪽 포인터 ptr.next에 대입함으로써 pre노드의 뒤쪽 포인터가 참조하는 곳을 p 다음 노드(=p 바로 다음에 위치한다)로 업데이트한다. 그 결과로 노드 p는 어디에도 참조되지 않고... 이는 즉 삭제가 완료되었다는 것을 의미한다.
일단 포인터부터 대입을 시켜주어야한다. 삭제할 노드 다음 노드의 포인터, 즉 link 부분을 삭제할 노드 이전 노드(pre 노드)의 link부분에 넣어준다. 한마디로 link부터 연결을 시켜 주는거지. 이러한 과정을 거치고 나면 순방향으로 data부분도 연결이 된다. pre 노드의 뒤쪽 link부분이 삭제한 노드 다음 노드의 data 를 참조하게 하는 것이다.
- 주목 노드 삭제
현재 주목하고 있는, 즉 현재 위치하고 있는 노드를 삭제한다. 주목 포인터 current가 참조하는 곳은 삭제한 노드의 앞쪽으로 업데이트한다.
*current를 remove()함수에 전달하여 처리
'Major > Data Structure & Algorithm' 카테고리의 다른 글
연결리스트 노드 개수 카운팅,특정 노드 순서 바꾸기,첫번째 노드 삭제하기 ... (0) | 2022.04.03 |
---|---|
[JAVA] 연결리스트, 노드, 삽입 및 삭제 (0) | 2022.04.03 |
배열 순차 자료구조, 선형 리스트, 다항식의 순차 자료구조 (0) | 2022.03.20 |
[2월 18일] Selection Sort Algorithm 삽입정렬, Insertion Sort Algorithm 삽입정렬 (0) | 2022.02.18 |
[2월 5일] 버블정렬 알고리즘, 문자수만큼 회전하기 (0) | 2022.02.15 |