자바에서 연결 리스트(Linked List)는 각 요소가 노드로 구성되어 있으며, 노드는 데이터와 다음 노드를 가리키는 포인터를 포함합니다. 연결 리스트는 삽입과 삭제가 빈번한 경우 배열보다 효율적일 수 있는 자료구조입니다. 자바에서 연결 리스트는 java.util.LinkedList 클래스로 구현됩니다.
– 자바 연결 리스트의 주요 특징
- 동적 크기(Dynamic Size):
- 연결 리스트는 필요에 따라 동적으로 크기가 조정됩니다.
- 요소를 추가하거나 제거할 때마다 크기가 자동으로 변경되므로, 배열처럼 크기를 미리 설정할 필요가 없습니다.
- 노드(Node) 구조:
- 연결 리스트는 노드라는 개별 요소들로 구성되며, 각 노드는 데이터와 다음 노드를 가리키는 포인터(참조)를 포함합니다.
LinkedList 클래스는 이중 연결 리스트(doubly linked list)로 구현되어, 각 노드는 이전 노드와 다음 노드를 가리킵니다.
- 삽입과 삭제의 효율성:
- 배열에 비해 중간에 요소를 삽입하거나 삭제하는 연산이 더 효율적입니다. 이는 요소를 이동시키지 않고 포인터만 변경하면 되기 때문입니다.
- 특정 위치에서 삽입 및 삭제는 O(1) 시간 복잡도를 가집니다(노드 참조가 주어진 경우).
- 임의 접근(Random Access)의 비효율성:
- 배열과 달리 연결 리스트는 인덱스를 사용하여 임의의 요소에 직접 접근할 수 없습니다.
- 특정 요소에 접근하려면 첫 번째 노드부터 순차적으로 접근해야 하므로, 평균적으로 O(n)의 시간 복잡도가 필요합니다.
- 메모리 사용:
- 연결 리스트는 각 노드가 데이터와 포인터를 저장하기 때문에 배열보다 더 많은 메모리를 사용합니다.
- 추가적인 포인터 저장 공간이 필요하므로 메모리 오버헤드가 발생합니다.
- 동일한 데이터 타입을 순서에 따라 관리하는 자료 구조
- 자료를 저장하는 노드에는 자료와 다음 요소를 가리키는 링크(포인터)가 있음
- 자료가 추가 될때 노드 만큼의 메모리를 할당 받고 이전 노드의 링크로 연결함 (정해진 크기가 없음)
- 연결 리스트의 i 번째 요소를 찾는게 걸리는 시간은 요소의 개수에 비례 : O(n)
- jdk 클래스 : LinkedList
public class MyListNode {
private String data;
public MyListNode next;
public MyListNode(){
this.data = null;
this.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;
}
}
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 tempNode = head;
while (tempNode.next != null){
tempNode = tempNode.next;
}
tempNode.next = newNode;
}
count++;
return newNode;
}
public MyListNode insertElement(int position, String data) {
int i;
MyListNode tempNode = head;
MyListNode newNode = new MyListNode(data);
if (position < 0 || position > count) {
System.out.println("추가 할 위치 오류 입니다. 현재 리스트의 개수는" + count + "개 입니다.");
return null;
}
if (position == 0){
newNode.next = head;
head = newNode;
}
else {
MyListNode preNode = null;
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;
if (position < 0 || position >= count){
System.out.println("삭제 할 위치 오류입니다. 현재 리스트의 개수는 " + count + "개 입니다." );
return null;
}
if (position == 0){
head = tempNode.next;
}
else {
MyListNode preNode = null;
for (i = 0; i < position; i ++){
preNode = tempNode;
tempNode = tempNode.next;
}
preNode.next = tempNode.next;
}
count--;
System.out.println(position + "번째 항복 삭제되었습니다.");
return tempNode;
}
public String getElement(int position) {
int i;
MyListNode tempNode = head;
if(position >= count ){
System.out.println("검색 위치 오류 입니다. 현재 리스트의 개수는 " + count +"개 입니다.");
return new String("error");
}
if(position == 0){ //맨 인 경우
return head.getData();
}
for(i=0; i<position; i++){
tempNode = tempNode.next;
}
return tempNode.getData();
}
public MyListNode getNode(int position) {
int i;
MyListNode tempNode = head;
if(position >= count ){
System.out.println("검색 위치 오류 입니다. 현재 리스트의 개수는 " + count +"개 입니다.");
return null;
}
if(position == 0){ //맨 인 경우
return head;
}
for(i=0; i<position; i++){
tempNode = tempNode.next;
}
return tempNode;
}
public void removeAll() {
head = null;
count = 0;
}
public int getSize() {
return count;
}
public void printAll() {
if(count == 0){
System.out.println("출력할 내용이 없습니다.");
return;
}
MyListNode temp = head;
while(temp != null){
System.out.print(temp.getData());
temp = temp.next;
if(temp != null){
System.out.print("->");
}
}
System.out.println("");
}
public boolean isEmpty() {
if(head == null) return true;
else return false;
}
}
public class MyLinkedListTest {
public static void main(String[] args) {
MyLinkedList list = new MyLinkedList();
list.addElement("A");
list.addElement("B");
list.addElement("C");
list.printAll();
list.insertElement(3, "D");
list.printAll();
list.removeElement(0);
list.printAll();
list.removeElement(1);
list.printAll();
list.insertElement(0, "A-1");
list.printAll();
System.out.println(list.getSize());
list.removeElement(0);
list.printAll();
System.out.println(list.getSize());
list.addElement("A");
list.printAll();
list.removeAll();
list.printAll();
list.addElement("A");
list.printAll();
System.out.println(list.getElement(0));
list.removeElement(0);
}
}
