Lab 02: Linked List

Data Structure 2023

1
List ADT
• An ordered sequence of element <A1, A2, A3, . . ., AN>

• List ADT (Abstract Data Type)

• Operations
• Insert, Delete …

• Implementation
1. Array
2. Linked List?

2
Linked List ADT

Header A1 A2 A3

• void Insert(ElementType X, List L, Position P)

• void Delete(ElementType X, List L)

• Position FindPrevious(ElementType X, List L)

• int* GetElements(List L)
○ Return an array containing all elements from the list to be printed out. (option p)

3
Linked List ADT
• List MakeEmpty(List L)
○ Make new header, element should be -1

• int IsEmpty(List L)
○ Check if list is empty or not.

• int IsLast(Position P, List L)

• Position Find(ElementType X, List L)

• void DeleteList(List L)
○ Delete the List

4
Insert
• Input Format
• ixy
• insert a new node with the key “x” after the node with the key “y”.
• i x -1
• insert a new node with the key “x” after the header node in the list.

• Implementation Details
• In the case of "i 2 7”, node "2" should be located at the NEXT of the node "7".
• In the case of location to be inserted is “-1” as "i 3 -1”, node “3” should be located at the
NEXT of HEAD of the LIST.
• If the key “x” already exists in the LIST, an error message should be printed out as follow
“insertion(”x”) failed : the key already exists in the list”
• If the key “y” does not exist in the LIST, an error message should be printed out.
• When insertion-error occurred, the format of the error messages should be
“insertion(“x”) failed : can not find the location to be inserted”.

5
Delete
• Input Format
• dx
• delete the node with the key “x”.

• Implementation Details
• In the case of “d 3”, node “3” should be deleted from the LIST.
• In the case of deleting a node(key “x”) which does not exist in the LIST, an error
message should be printed out.
• When deletion-error occurred, the format of the error messages should be
“deletion(“x”) failed : element “x” is not in the list”.

6
Find
• Input Format
• fx
• print the key of the previous node of the node with the key “x”.

• Implementation Details
• In the case of “f 2”, the previous node(key “y”) information of node “2” should be
printed out as follows :
“key of previous node of 'x” is “y””,
“key of previous node of “x” is head”
• In the case of searching for a node which does not exist in the LIST, an error message
should be printed out.
• When a finding-error occurred, the format of the error messages should be
“finding(“x”) failed : element “x” is not in the list” as above.

7
PrintList
• Input Format
• p
• print the entire list from the beginning to the end.

• Implementation Details
• In the case of “p”, the entire LIST should be printed out and the space between keys is
one space.
• Printing order should be started from the NEXT of HEAD, and if the LIST is empty,
“empty list!” should be printed out.
• Return an array that contains the elements of the list using the GetElements function

8
Linked List ADT
Structure Function
typedef struct Node *PtrToNode; List MakeEmpty( List L );
typedef PtrToNode List;
typedef PtrToNode Position; int IsEmpty( List L );
typedef int ElementType; int IsLast( Position P, List L );
struct Node void Insert( ElementType X, List L, Position P );
{
ElementType element; int* GetElements(List L);
Position next;
void Delete( ElementType X, List L );
};
Position Find(ElemenType X, List L );
Position FindPrevious ( ElementType X, List L );
void DeleteList ( List L );

9
Linked List - Skeleton Code
Prototype & struct

10
Linked List Input & Output Example

11
Submission
• File Name Format
- [StudentID].c
- ex) 20XXXXXXXX.c

• Execution
- gcc 20XXXXXXXX.c –o 20XXXXXXXX
- ./20XXXXXXXX [input_file_name] [output_file_name]
- Run your solution code with the provided test case above and check whether it works
properly

• Directory Format
- 2023_CSE2010_20XXXXXXXX
└── lab02
└── 20XXXXXXXX.c
12
Assignment
• Due
- ~ 2023.03.22 23:59
- Last Commit 기준

• 자세한 내용은 과제 명세 PDF 파일 참고

13