【Definition】An Abstract Data Type (ADT) is a data type that is organized in such a way that the specification on the objects and specification of the operations on the objects are separated from the representation of the objects and the implementation on the operations.
typedef struct list_node *list_ptr; typedef struct list_node {
char data [ 4 ] ;
N1->next = N2 ; N2->next = NULL ; ptr = N1 ;
list_ptr next ;
}; list_ptr ptr ;
array+i array+i+1
……
itemi itemi+1 ……
MaxSize has to be estimated.
Find_Kth takes O(1) time.
Insertion and Deletion not
only take O(N) time, but also involve a lot of data movements which takes time.
2. Linked Lists
Address
0010 0011 0110 1011
Data
SUN QIAN ZHAO
LI
Pointer
1011 0010 0011 NULL
ptr ZHAO
§2 The List ADT
QIAN
SUN
LI
NULL
To link ‘ZHAO’ and ‘QIAN’:
Head pointer ptr = 0110
ptr
ZHAO
QIAN
NULL
Insertion
ptr
a1
node
... ai
§2 The List ADT takes O(1) time.
ai+1
... an
NULL
temp->next =
node->next
b temp
node->next = temp
Question: What will happen if the order of the two steps is reversed?
list_ptr N1, N2 ;
N1 = (list_ptr)malloc(sizeof(struct list_node));
Initialization:
Locations oNNf12-t=>hd(elaistant_=opdt‘Zr)eHmsAaOmllo’ ;ac(ysizeof(struct list_node)); change onNd2-i>fdfaetrae=n‘tQIrAuNn’ ;s.
Finding previous of the current item from a list.
1. Simple Array implementation of Lists
§2 The List ADT
array[ i ] = itemi
Address Content
……
……
Sequential mapping
§2 The List ADT
❖ ADT:
Objects: ( item0, item1, , itemN1 )
Operations:
Finding the length, N, of a list. Printing all the items in a list.
Why after?
Making an empty list.
Doubly Linked Circular Lists
§2 The List ADT
typedef struct node *node_ptr ; typedef struct node {
llink
rlink
• item •
A} ;donenulooebddmleeye__nppltttirrnklriltlieeinndmkk;;;circMuTiltaWNhsSgyreogupBebhtlnwotprihe1uyUsetpfy-efttyhhvid>rhoonhowmioeoo2ushoduewmei-m-uehyytt>attnwhysh,ohwh-r3.toow.tueaehnWeh-.honuu>neohdTIeaaupog…n’tdhayhoss1thldrlhtkdoodkeyluaaesDeed-pdetghvbnm?>tdynmdoodteohienelromoooney?IaIeeotu=fa=dlu’’d.w?oerdllwtmeslip1plotaenei:f:weaht?tnm-sc-irkratnn)ntaheo--he>g>dtevdethdtlarheenlealaaiidien?lonntlviokrdsk1.ee-te-s>s>at.?rldllniiynno?kkde
Questnioonde: How can we delete the first node from a list?
Answer: We can add a dummy head node to a list.
Read programs in Figures 3.6-3.15 for detailed implementations of operations.பைடு நூலகம்
Question: How can we insert a new first item?
Deletion
ptr
a1
pre
... ai
§2 The List ADT takes O(1) time.
ai+1
... an
NULL
pre->next =
b
node->next
free ( node )
Finding the k-th item from a list, 0 k < N.
Inserting a new item after the k-th item of a list, 0 k < N.
Deleting an item from a list.
Finding next of the current item from a list.
CHAPTER 3 Lists, Stacks, and Queues
§1 Abstract Data Type (ADT)
【Definition】Data Type = { Objects } { Operations }
〖Example〗 int = { 0, 1, 2, , INT_MAX, INT_MIN } { , , , , , }