3.연결 리스트(LinkedList)구현

LinkedList 특징

- 동일한 데이터 타입을 순서에 따라 관리하는 자료구조

- 자료를 저장하는 노드에는 자료와 다음 요소를 가리키는 링크(포인터)가 있음

- 자료가 추가 될때 노드만큼의 메모리를 할당받고 이전 노드의 링크로 연결함(정해진 크기가 없음)

- 연결리스트의 i번째 요소를 찾는게 걸리는 시간은 요소의 개수에 비례 : O(n)

- jdk 클래스 : LinkedList

 

LinkedList 구현

- MyListNode.java

public class MyListNode {

private String data; // 자료 
public MyListNode next; // 다음 노드를 가리키는 링크

public MyListNode() {
data = null;
next = null;
}

public MyListNode(String data) {
this.data = data;
this.next = null;
}

public MyListNode(String data, MyListNode link) {
this.data = data;
this.next = link;
}

public String getData() {
return data;
}
}

 

- MyLinkedList.java

public class MyLinkedList {

private MyListNode head;
int count;

public MyLinkedList() 
{
head = null;
count = 0;
}

public MyListNode addElement(String data)
{
MyListNode newNode;

if(head == null) {
newNode = new MyListNode(data);
head = newNode;
}
else {
newNode = new MyListNode(data);
MyListNode temp = head;
while(temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
}

count++;

return newNode;
}

public MyListNode insertElement(int position, String data)
{
int i;
MyListNode tempNode = head;
MyListNode preNode = null;

MyListNode newNode = new MyListNode(data);

if(position < 0 || position > count ) {
return null;
}

if(position == 0) {
newNode.next = head;
head = newNode;
}

else {
for(i = 0; i < position; i++) {
preNode = tempNode;
tempNode = tempNode.next;
}
newNode.next = preNode.next;
preNode.next = newNode;
}

count++;
return newNode;

}

public MyListNode removeElement(int position)
{
int i;

MyListNode tempNode = head;
MyListNode preNode = null;

if(position == 0) {
head = tempNode.next;
}
else {

for(i = 0; i < position; i++) {
preNode = tempNode;
tempNode = tempNode.next;
}

preNode.next = tempNode.next;

}
count --;
return tempNode;

}



}