[자료구조] 선형 연결리스트
연결 리스트 (Linked list)
- 연결리스트는 연속된 노드들로 이루어진다.
- 노드는 자료를 저장하는 data feild와 다음 노드의 주소를 가리키는 link field로 이루어진다.
1. 단순 연결 리스트
노드 클래스
- 멤버변수
data
는 String변수로써 노드에 데이터를 담는 역할을 한다. - 멤벼변수
link
는 다음 노드를 저장하는 역할로 사용되는 변수로,ListNode
자기 자신을 변수형태로 사용한다. - 각각의 생성자는 매개변수의 종류에 따라 다른 역할로 사용된다.
getData()
: 해당 노드가 가지고 있는data
를 반환한다.
연결 리스트 클래스
head
: 리스트 안에서 가리키고 있는 자료의ListNode
이다.insertMiddleNode(ListNode, String)
: 특정 노드 다음 노드에 자료를 삽입한다.insertLastNode(String)
: 리스트의 마지막에 새로운 노드를 삽입한다.deleteLastNode()
: 리스트의 마지막 노드를 삭제하는 메소드이다.searchNode(String)
: String 매개변수를 입력으로 받아, 그 값에 해당하는 노드를 반환한다.
중간 노드 삽입 알고리즘
public void insertMiddleNode(ListNode pre, String data)
{
ListNode newNode = new ListNode(data); // (1)
newNode.link = pre.link; // (2)
pre.link = newNode; // (3))
}
- (1) 과정 :
newNodeM
를 생성하고,pre
노드는 리스트의 어딘가에 존재한다.
- (2) 과정 :
newNode
의 link에 pre.link를 대입함으로써, newNode의 다음 노드가 pre의 다음노드와 같게 한다.
- (3) 과정 : pre의 다음노드가 newNode를 가리키게 함으로써 최종적으로 pre와 node3 사이에 newNode가 삽입되도록 한다.
- 삽입 결과
마지막 노드 삽입 알고리즘
public void insertLastNode(String data)
{
ListNode newNode = new ListNode(data);
if(head == null)
{
this.head = newNode; // (1)
}
else
{
ListNode temp = head; // (2)
while(temp.link != null)
temp = temp.link; // (3)
temp.link = newNode; // (4)
}
}
- (1) 과정 : 리스트가 비어있는 경우, 새로운 노드를 head 포인터에 바로 집어넣는다.
- (2) 과정 : 리스트의 끝을 탐색하기 위해, temp 노드를 생성한다.
- (3) 과정 : temp 노드를 뒤로 이동시키며, 리스트의 끝을 찾는다.
- (4) 과정 : temp 노드가 리스트의 끝에 도달했을때, newNode를 temp의 뒤에 연결시킨다.
마지막노드 삭제 알고리즘
public void deleteLastNode()
{
ListNode pre;
ListNode temp;
if(head == null) // (1)
return;
if(head.link == null) // (2)
{
head = head.link;
}
else
{
pre = head;
temp = head.link; // (3)
while(temp.link != null)// (4)
{
pre = temp;
temp = temp.link;
}
pre.link = null; //(5)
}
}
- (1) 과정 : 리스트가 비어있다면 아무것도 하지 않는다.
- (2) 과정 : 노드가 두개면 첫 노드를 마지막 노드로 변경하여, 두번째 노드를 지운다
- (3) 과정 : pre와 temp노드를 연달아 배치한다. temp는 삭제될 노드이고, pre는 마지막 노드가 될 노드이다.
- (4) 과정 : pre와 temp를 뒤로 한노드씩 이동시키며, temp가 마지막 노드가 되는 시점을 찾는다.
- (5) 과정 : while문 안의
temp = temp.link
에서 temp는 null이 되었으므로 삭제되었다. pre의 다음노드를 null로 지정하여 temp의 삭제를 마무리한다.
Author And Source
이 문제에 관하여([자료구조] 선형 연결리스트), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@16fekim/자료구조-선형-연결리스트저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)