[go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • 31 views

    CDS M7 1

    Uploaded by

    Naomi Belonio
    This document discusses linked lists, including their basic concepts and operations. It defines a linked list as a linear data structure where elements are not stored at contiguous memory locations, but rather are linked using pointers. The core linked list operations are described as insertion, deletion, traversal, and finding an element. The document then provides steps to implement a linked list in Python by creating Node and LinkedList classes, and defining methods for adding and removing nodes, finding elements, and traversing the list. Sample code is given to test the linked list implementation.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd

    CDS M7 1

    Uploaded by

    Naomi Belonio
    31 views15 pages
    This document discusses linked lists, including their basic concepts and operations. It defines a linked list as a linear data structure where elements are not stored at contiguous memory locations, but rather are linked using pointers. The core linked list operations are described as insertion, deletion, traversal, and finding an element. The document then provides steps to implement a linked list in Python by creating Node and LinkedList classes, and defining methods for adding and removing nodes, finding elements, and traversing the list. Sample code is given to test the linked list implementation.

    Original Description:

    Original Title

    CDS-M7-1

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses linked lists, including their basic concepts and operations. It defines a linked list as a linear data structure where elements are not stored at contiguous memory locations, but rather are linked using pointers. The core linked list operations are described as insertion, deletion, traversal, and finding an element. The document then provides steps to implement a linked list in Python by creating Node and LinkedList classes, and defining methods for adding and removing nodes, finding elements, and traversing the list. Sample code is given to test the linked list implementation.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    31 views15 pages

    CDS M7 1

    Uploaded by

    Naomi Belonio
    This document discusses linked lists, including their basic concepts and operations. It defines a linked list as a linear data structure where elements are not stored at contiguous memory locations, but rather are linked using pointers. The core linked list operations are described as insertion, deletion, traversal, and finding an element. The document then provides steps to implement a linked list in Python by creating Node and LinkedList classes, and defining methods for adding and removing nodes, finding elements, and traversing the list. Sample code is given to test the linked list implementation.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    of 15

    Linked Lists

    Froilan De Guzman
    Learning outcomes:
    - To discuss the basic concepts of linked list structure.
    - To discuss the basic operations of linked list
    - To develop class in Python behaves linked list data
    structures.

    2
    What is linked list?
    A linked list is a linear data structure, in which the elements are not stored at
    contiguous memory locations. The elements in a linked list are linked using
    pointers as shown in the below image:
    https://www.geeksforgeeks.org/data-structures/linked-list/

    ROOT
    In simple words, a linked list consists of nodes where each node contains a
    data field and a reference(link) to the next node in the list.

    3
    Basic linked list operations
    Insertion − Adds an element at the
    beginning of the list.
    Delete − Deletes an element using the
    given key.
    Traverse − Displays the complete list.
    Find − Searches an element using the
    given key.
    Source:
    https://www.tutorialspoint.com/data_structures_algorithms/linked_list_algorithms.
    htm

    4
    Insertion Operation

    ROO ROO
    T T

    ROO
    T ROO
    T

    Source: https://www.tutorialspoint.com/data_structures_algorithms/linked_list_algorithms.htm
    5
    Deletion Operation

    ROO ROO
    T T

    ROO ROO
    T T
    Source: https://www.tutorialspoint.com/data_structures_algorithms/linked_list_algorithms.htm
    6
    Linked list in Python
    • Step 1: Create node class
    class node:
    def __init__(self, d, n):
    self.data = d
    self.nextNode = n

    7
    Linked list in Python
    • Step 2: Create methods for node class
    class node:
    def __init__(self, d, n):
    self.data = d
    self.nextNode = n
    def getNext(self):
    return self.nextNode
    def setNext(self, n):
    self.nextNode = n
    def getData(self):
    return self.data
    def setData(self, d):
    self.data = d
    8
    Linked list in Python
    • Step 3: Create linked list class
    class linkedList:
    def __init__(self):
    self.root = None
    self.size = 0

    9
    Linked list in Python
    • Step 4: Create add method
    class linkedList:
    def __init__(self):
    self.root = None
    self.size = 0
    def add(self, d):
    newNode = node(d, self.root)
    self.root = newNode
    self.size +=1

    10
    Linked list in Python
    • Step 5: Create remove/delete method
    def remove(self, d):
    thisNode = self.root
    prevNode = None
    while thisNode is not None:
    if thisNode.getData() == d:
    if prevNode is not None:
    prevNode.setNext(thisNode.getNext())
    else:
    self.root = thisNode.getNext()
    self.size-=1
    return True #data removed
    else:
    prevNode = thisNode
    thisNode = thisNode.getNext()
    return False #data not found 11
    Linked list in Python
    • Step 6: Create find method
    def find(self, d):
    thisNode = self.root
    while thisNode is not None:
    if thisNode.getData() == d:
    return d
    elif thisNode.getNext() == None:
    return False
    else:
    thisNode = thisNode.getNext()

    12
    Linked list in Python
    • Step 7: Create display method
    def traverse_list(self):
    if self.root is None:
    print("List has no element")
    return
    else:
    n = self.root
    while n is not None:
    print(n.data)
    n = n.nextNode
    def getSize(self):
    return self.size

    13
    Linked list in Python
    • Step 8: Test your linked lists
    myList = linkedList()
    myList.add(4)
    myList.add(2)
    myList.add(5)
    myList.add(10)
    myList.add(1)
    print ("Order of List: ", myList.traverse_list())
    print ("The size is: ", myList.getSize())
    myList.remove(2)
    myList.remove(15)
    print ("The size is: ", myList.getSize())
    print (myList.find(11))
    myList.add(12)
    print ("Order of List: ", myList.traverse_list())
    14
    References:
    - https://www.geeksforgeeks.org/data-structures/linked-list/
    - https://www.tutorialspoint.com/data_structures_algorithms/linked_list_algorithms.htm

    15

    You might also like