리스트,list

Operations
데크,deque와의 비교
deque list
add_first(x) add(0, x)
remove_first() remove(0)
add_last(x) add(size(), x)
remove_last() remove(size() - 1)

연결리스트,linked_list
{
node들을
포인터,pointer로 연결하며
리스트 item 하나하나마다 포인터가 들어있어서 서로 연결을....

단일? 단순? singly_linked_list
{
단일연결리스트

item(node) 하나마다 포인터가 next 하나만 있다. 한 방향으로만 traverse 가능.
}
이중연결리스트 doubly_linked_list
{
item(node) 하나마다 포인터가 prev, next 두 개 있다. 양방향으로 traverse 가능.

}

내생각 대충임, chk
* time_complexity 가 random_access 에 불리하다
* size(bound)가 flexible 하다 - 배열,array, 등 고정적인 크기를 가진 것 보다
* 삽입 삭제도 flexible 하다 - insert, delete time_complexity 가 O(1)이다 - 가장 큰 장점?
* head와 tail 포인터를 별도로 만들기도 만들지 않기도 하는데 만드는 게 편하다
*
tmp delme. diagram을 그릴때 ... ( used https://asciiflow.com/ )
     ┌────────────┐                   ┌──────────┐
     │            │                   │          │
     │  data      │              ◄────┤  prev    │
     │            │                   ├──────────┤
     ├──────┬─────┤                   │          │
     │      │     │                   │  data    │
◄────┤ prev │ next├────►              │          │
     │      │     │                   ├──────────┤
     └──────┴─────┘                   │          │
                                      │  next    ├───►
                                      └──────────┘
어떤 algorithm을 서술하느냐에 따라 뭐가 적당한지가 다르다
화살표가 너무 많아 복잡해져서 왼쪽이 아닌 오른쪽이 적당할 때가 있다


Linus Torvalds' good taste argument for linked lists, explained
https://github.com/mkirchner/linked-list-good-taste
https://news.ycombinator.com/item?id=25326552

AKA 링크드 리스트, 링크트 리스트, 연결된 리스트[1], 연결 목록[2]
}

skip_list - 작성중



Up: 리스트,list functional_programming? functional_PL?
}


nlab 'lists' redir to 자유모노이드,free_monoid { writing; curr see WpEn:Free_monoid Google:free.monoid }

Compare 튜플,tuple
{
tuple과 list의 비교 표 (Haskell wiki)
https://wiki.haskell.org/Heterogenous_collections#The_problem
}

"the (potentially) infinite analog of a list is a stream."[3]
compare 스트림,stream
{
RR:스트림,stream
}


AKA 목록




/// tmp ///
WpEn:List_(abstract_data_type) - list or sequence (시퀀스,sequence page mk? 같은영단어 수열,sequence)
corresp interwiki ko : WpKo:리스트_(컴퓨팅)