Scribd
Upload
15 views2 pages

Linked Lists: Search, Insert, Delete Methods

The document discusses linked lists and common operations on them. It describes: - Doubly linked lists where each element has pointers to the next and previous elements. - Common operations like search, insert, and delete and their time complexities. For example, search takes O(n) time in the worst case to traverse the entire list, while insert and delete take O(1) time in a doubly linked list. - The differences in supporting these operations between singly and doubly linked lists. For example, delete takes O(n) time in a singly linked list since it lacks pointers to the previous element.

Uploaded by

MEHUL RATHOD
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
15 views2 pages

Linked Lists: Search, Insert, Delete Methods

The document discusses linked lists and common operations on them. It describes: - Doubly linked lists where each element has pointers to the next and previous elements. - Common operations like search, insert, and delete and their time complexities. For example, search takes O(n) time in the worst case to traverse the entire list, while insert and delete take O(1) time in a doubly linked list. - The differences in supporting these operations between singly and doubly linked lists. For example, delete takes O(n) time in a singly linked list since it lacks pointers to the previous element.

Uploaded by

MEHUL RATHOD
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Winter 2020 Lecture Five ITEC2620

1 Linked Lists
A linked list is a data structure in which the objects are arranged in a linear order. Each
element in a doubly linked list L is an object with a key field and two other pointer fields:
next and prev. Given an element x in the list, next[x] points to its successor in the linked list,
and prev[x] points to its predecessor. If prev[x] = N IL , the element x has no predecessor
and is therefore the first element or head of the list. If next[x] = N IL, the element x has no
successor and is therefore the last element, or tail of the list. An attribute head[L] points to
the first element of the list. If head[L] = N IL, the list is empty.

Consider a doubly linked list L. The procedure ListSearch(L, k) finds the first element with
key k in list L, returning a pointer to this element. If no object with key k appears in the
list, then N IL is returned. The procedure takes Θ(n) time in the worst-case, since it may
have to search the entire list.

ListSearch(L, k)
1: x <- head[L]
2: while (x != NIL and key[x] != k)
3: x <- next[x]
4: return x

Given an element x whose key field has already been set, the ListInsert procedure inserts
x onto the front of the linked list. The running time is Θ(1).

ListInsert(L, x)
1: next[x] <- head[L]
2: if head[L] != NIL
3: then prev[head[L]] <- x
4: head[L] <- x
5: prev[x] <- NIL

The procedure ListDelete removes an element x from L. A pointer to x is given, and it


then delete x out of L by updating pointers. The procedure runs in Θ(1) time. If we wish to
delete an element with a given key, ListSearch is called to retrieve a pointer to the element.
In that case, Θ(n) time is required in the worst case.
To figure out how the algorithm works, one would consider two example cases, no element
in the list (i.e., head[L] == NIL), and there are elements in the list i.e., head[L] != NIL).

ListDelete(L, x)
1: if prev[x] != NIL
2: then next[prev[x]] <- next[x]
3: else head[L] <- next[x]
4: if next[x] != NIL
5: then prev[next[x]] <- prev[x]

What if L is singly linked list?


Data Structure SEARCH INSERT DELETE
singly linked list Θ(n) Θ(1)? Θ(n)??
doubly linked list Θ(n) Θ(1)? Θ(1)

1
Winter 2020 Lecture Five ITEC2620

?) If replacement is required (to ensure that keys are distinct), then it takes Θ(n) instead.
??) An element in a singly linked list does not store information of its predecessor, which
is needed for deletion to ensure that elements are still linked after the deletion. This takes
Θ(n) time.
To figure out how the algorithm works, one would consider four example cases,

• prev[x] != NIL and next[x]!=NIL, where lines 2,5 are executed, there are at least
three elements, and x the element to be deleted is at the middle;

• prev[x] == NIL and next[x]!=NIL, where lines 3,5 are executed, there are at least
two elements, and x is the head;

• prev[x] != NIL and next[x]==NIL, where line 2 is executed, there are at least two
elements, and x is the tail;

• prev[x] == NIL and next[x]==NIL, where line 3 is executed, and x is the only ele-
ment in the list.

You might also like