Linked List

Must Know Concept이다 하나씩 해보자

Linked Lists

출처: https://opentutorials.org/module/1335/8857

• Linked Lists
  • 정의
    • linear collection of data elements, called nodes, each pointing to the next node by means of a pointer
    • consisting of a group of nodes which together represent a sequence.
    • each node is composed of data and a reference(link)
  • 구현
  • 사용
    • efficient insertion or removal of elements from any position in the sequence during iteration
  • 어디에 쓰기 적합
    • implement sever other common abstract data types. including lists ,stacks, queue, associative arrays, and S-expression
    • 아무 지점에서나 삽입이나 삭제가 가능하다
    • Program 이 돌아갈동안 allocation and deallocation memory가 가능합니다
    • 초기의 size에 대해 정의할 필요가 없다
  • 단점
    • 배열보다 더 많은 메모리가 쓰인다(포인터 때문에)
    • sequence라서 항상 처음부터 읽힌다
    • 비연속적으로 저장되있어서 각각의 element에 접근할 때  시간이 든다
      • CPU cache
    • reverse traversing 할 때 cubersome한다
  • 종류
    • Singly linked list
      • next pointer을 가지고있다.
      • insertion
      • deletion
      • traversal
    • Doubly linked list
      • previous node에 대한 포인터도 가지고있다.
      • https://upload.wikimedia.org/wikipedia/commons/thumb/5/5e/Doubly-linked-list.svg/610px-Doubly-linked-list.svg.png
  • time and space complexity
    • indexing
      • o(n)
    • insert at beginning
      • o(1)
    • inset/delete at end
      • o(n) unknown
      • 1 known
    • insert in middle
      • search time+ 1
    • wasted space
      • n

Time Complexity

 

Space              O(n)          O(n)

Search           O(logn)      O(n)

Insert            O(logn)        O(n)

Delete            O(logn)       O(n)

 

구현 해보자

~~~java

public class LinkedList {

private Node head;

private Node tail;

private int size=0;

private class Node

{

private Object data;  //데이터가 저장될 필드

private Node next;

public Node(Object input)

{

this.data=input;

this.next=null;

}

public String toString() { //노드의 내용을 출력해보는 코드

return String.valueOf(this.data);

}

public void addFirst(Object input){

Node newNode= new Node(input);

newNode.next=head;

head=newNode;

size++;

if(head.next==null){

tail=head;

}

public void add (int k, Object input){

if(k==0){

addFirst(input);

}

else{

Node temp1=node(k-1);

Node temp2=temp1.next;

Node newNode=new Node(input);

temp1.next= newNode;

newNode.next =temp2;

size++;

if(newNode.next==null){

tail=newNode;

}

}

}

public class Main {

public static void main(String[] args){

LinkedList numbers= new LinkedList();

}

}

python  출처

#!/usr/bin/python
class Node:
def init(self, data, next=None):
self.data = data
self.next = next

def init_list():
global node1
node1 = Node(1)
node2 = Node(2)
node3 = Node(3.33333)
node4 = Node(“four”)
node1.next = node2
node2.next = node3
node3.next = node4

def delete_node(del_data):
global node1
pre_node = node1
next_node = pre_node.next

if pre_node.data == del_data:
node1 = next_node
del pre_node
return

while next_node:
if next_node.data == del_data:
pre_node.next = next_node.next
del next_node
break
pre_node = next_node
next_node = next_node.next

def insert_node(ins_data):
global node1
new_node = Node(ins_data)
new_node.next = node1
node1 = new_node

def print_list():
global node1
node = node1
while node:
print node.data,
node = node.next
print

def Main():
init_list()
delete_node(2)
insert_node(“new”)
print_list()

Main()