Scribd Logo
Upload

Welcome to Scribd!

  • 28 views

    Singly Linked Lists: CS235-Data Structures

    Uploaded by

    V S Naidu P
    Singly linked lists store elements in memory using individual nodes that link to the next node in the linear sequence. Each node contains a reference to the element and a reference to the next node. The first and last nodes are called the head and tail. Traversing the list involves starting at the head and following each node's next reference until reaching the tail, which has no next reference. Elements can be inserted or removed at the head, tail, or any position in the list by adjusting the next references between nodes.

    Copyright:

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

    Singly Linked Lists: CS235-Data Structures

    Uploaded by

    V S Naidu P
    28 views22 pages
    Singly linked lists store elements in memory using individual nodes that link to the next node in the linear sequence. Each node contains a reference to the element and a reference to the next node. The first and last nodes are called the head and tail. Traversing the list involves starting at the head and following each node's next reference until reaching the tail, which has no next reference. Elements can be inserted or removed at the head, tail, or any position in the list by adjusting the next references between nodes.

    Original Description:

    Notes on Singly linked list

    Original Title

    singlylinkedlist

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Singly linked lists store elements in memory using individual nodes that link to the next node in the linear sequence. Each node contains a reference to the element and a reference to the next node. The first and last nodes are called the head and tail. Traversing the list involves starting at the head and following each node's next reference until reaching the tail, which has no next reference. Elements can be inserted or removed at the head, tail, or any position in the list by adjusting the next references between nodes.

    Copyright:

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

    Singly Linked Lists: CS235-Data Structures

    Uploaded by

    V S Naidu P
    Singly linked lists store elements in memory using individual nodes that link to the next node in the linear sequence. Each node contains a reference to the element and a reference to the next node. The first and last nodes are called the head and tail. Traversing the list involves starting at the head and following each node's next reference until reaching the tail, which has no next reference. Elements can be inserted or removed at the head, tail, or any position in the list by adjusting the next references between nodes.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    You are on page 1of 22

    Singly Linked lists

    CS235-Data structures
    Both array-based sequences and linked lists keep elements in a
    certain order, but using a very different style.

    • An array provides the more centralized representation, with one large


    chunk of memory capable of accommodating references to many
    elements.
    • A linked list, in contrast, relies on a more distributed representation
    in which a lightweight object, known as a node, is allocated for
    each element.
    Each node maintains a reference to its element and one or more
    references to neighboring nodes in order to collectively represent the
    linear order of the sequence.

    3
    Singly Linked Lists
    Singly Linked Lists
    Definition
    A singly linked list, in its simplest form, is a collection of nodes that
    collectively form a linear sequence. Each node stores a reference to
    an object that is an element of the sequence, as well as a reference
    to the next node of the list

    4
    Singly Linked Lists

    Definition : head and tail


    The first and last node of a linked list are known as the head and
    tail of the list, respectively.

    Definition : traverse
    By starting at the head, and moving from one node to another by
    following each node’s next reference, we can reach the tail of the
    list. We can identify the tail as the node having None as its next
    reference. This process is commonly known as traversing the linked
    list.

    5
    Singly Linked Lists

    6
    Creating a linked list

    • class Node():
    • def __init__(self, data):
    • self.data = data
    • a = Node(10)
    • b = Node(20)
    • a.next = b
    • b.next = None
    • print(a.data)
    • print(a.next.data)
    Singly Linked Lists
    Inserting an Element at the Head of a Singly
    Linked List
    Inserting an Element at the Head of a Singly Linked
    List
    How to insert an element at the head of the
    list?

    9
    Inserting an Element at the Head of a Singly
    Linked List

    1. create a new node,


    set its element to the new element,
    set its next link to the current head;

    2. set the list’s head to point to the


    new node.

    10
    Inserting an Element at the Head of a Singly Linked
    List

    INSERT_AT_BEGINNING(L, n)
    n.next = L.head
    L.head = n

    11
    Singly Linked Lists
    Inserting an Element at the tail of a Singly Linked
    List
    Inserting an Element at the tail of a Singly
    Linked List
    We can also easily insert an element at the tail of the list, provided
    we keep a reference to the tail node.

    12
    Inserting an Element at the tail of a Singly Linked
    List

    INSERT_AT_LAST(L, n)
    temp = L.head
    while(temp.next != null)
    temp = temp.next

    temp.next = n

    13
    Singly Linked Lists
    Inserting an Element at random position of a Singly
    Linked List
    Inserting an Element at random position of a
    Singly Linked List
    We can also easily insert an element at the tail of the list, provided
    we keep a reference to the tail node.

    12
    Inserting an Element at random position of a Singly
    Linked List

    INSERT_NODE_AFTER(n, a)
    n.next = a.next
    a.next = n

    13
    Singly Linked Lists
    Removing an Element of a Singly Linked List
    Removing an Element at the head of a Singly
    Linked List

    Removing an element from the head of a singly linked list is


    essentially the reverse operation of inserting a new element at the
    head.

    14
    Removing an Element at the head of a Singly
    Linked List
    Removing an element from the head of a singly linked list is
    essentially the reverse operation of inserting a new element at the
    head.

    14
    Removing an Element at the tail of a Singly
    Linked List

    15
    Removing an Element at random position of
    a Singly Linked List

    15

    You might also like