KEMBAR78
L I N K e D: Linked List | PDF | Array Data Structure | Pointer (Computer Programming)
Scribd
Upload
231 views11 pages

L I N K e D: Linked List

The document discusses linked lists and their advantages over arrays. Linked lists store elements in individual nodes that contain both data and a pointer to the next node. This allows elements to be easily inserted or removed without rearranging the entire structure. The key aspects are that each node contains data and a link to the next node, lists are accessed through a starting pointer, and a null pointer indicates the end of the list. Common linked list operations like traversing, inserting, deleting and updating elements are also presented.

Uploaded by

Bilo Bilo
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
231 views11 pages

L I N K e D: Linked List

The document discusses linked lists and their advantages over arrays. Linked lists store elements in individual nodes that contain both data and a pointer to the next node. This allows elements to be easily inserted or removed without rearranging the entire structure. The key aspects are that each node contains data and a link to the next node, lists are accessed through a starting pointer, and a null pointer indicates the end of the list. Common linked list operations like traversing, inserting, deleting and updating elements are also presented.

Uploaded by

Bilo Bilo
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 11

L i

n k

e
d

Linked List
www.eshikshak.co.in

Limitations of Array
To insert or remove an element at an interior location in an ArrayList requires shifting of data and is an O(n) operation.

www.eshikshak.co.in

Limitations of Array
An array has a limited number of elements
routines inserting a new value have to check that there is room Cant increase or decrease its size during execution

Can partially solve this problem by reallocating the array as needed (how much memory to add?)
adding one element at a time could be costly

one approach - double the current size of the array

Array elements are stored in contiguous memory locations


Always we wont have enough contiguous memory

Q: how do we know what is part of the array?


A: have the elements keep track of each other use pointers to connect the elements together as a LIST of things
www.eshikshak.co.in

Introduction to Linked List


It is linear collection of data items, called nodes where linear order is maintain by means of pointers

Data

Link

Where each item contains two parts or fields


Data : Information or actual value of an element

Link : It contains the address to its successor (and sometimes its predecessor)

www.eshikshak.co.in

Introduction to Linked List


How to define the linked list data strcture in C Data Link

struct linklist { int data;

struct linklist *link;


}

www.eshikshak.co.in

Introduction to Linked List


list S 45 O 45 22 N 22 99 U 99
NULL

The entire linked list is accessed from an external pointer list that points to first node in the list The link field of the last node in the list contains a special value, known as NULL The NULL pointer is used to signal the end of a list

www.eshikshak.co.in

Introduction to Linked List


list S 45 O 45 22 N 22 99 U 99
NULL

The list with no nodes on it is called the empty list or the null list A list can be initialized to the empty list by list = NULL

Need way to indicate end of list (NULL pointer)


Need to know where list starts (first element) Each element needs pointer to next element (its link) Need way to allocate new element (use malloc) Need way to return element not needed any more (use free) Divide element into data and pointer

www.eshikshak.co.in

Types of Linked List


list S 45 O 45 22 N 22 99 U 99
NULL

There are 4 different kinds of linked lists:


Linear singly linked list
Circular singly linked list Two way or doubly linked list

Circular doubly linked list.

www.eshikshak.co.in

Types of Linked List


list S 45 O 45 22 N 22 99 U 99
NULL

The basic operations of Linked List Traverse Insert At Beginning At End At given position Delete At Beginning At End At given position Update At Beginning At End At given position www.eshikshak.co.in

Sample Linked List Operations


Struct linklist { int data; Struct linklist *next; }
Pictorially
ListStart

In Memory
ListStart 0 100

ListStart = (linklist *) malloc(sizeof(linklist)); /* ListStart points to memory allocated at location 108 */


ListStart ? ? Data Next
www.eshikshak.co.in

ListStart Data Next 108 ? ? 100 108

Sample Linked List Operations (cont)


ListStart->data = 5;
ListStart 5 ? ListStart 108 5 100 108 ?

ListStart->next = NULL;
ListStart 5 ListStart 108 5 100 ListStart 5 ? ? 108 0

ListStart->next = (EPtr) malloc(sizeof(EStruct));


ListStart 108 5 100 108 120 ? 120 ?

ListStart->next->data = 9; ListStart->next->next = NULL;


ListStart 5 9 ListStart 108 5 100 108 120 9 120 0

You might also like