KEMBAR78
Week1-Linked List | PDF | Array Data Structure | Information Retrieval
Scribd
Upload
119 views12 pages

Week1-Linked List

A linked list is a data structure where each element, called a node, contains data and a pointer to the next node. This allows dynamic memory allocation and easy insertion/deletion without shifting entries. The document discusses the motivation for linked lists by comparing to arrays, describes the components of nodes, and provides an implementation of a Node class to represent the nodes in a linked list.

Uploaded by

lindytindylindt
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
119 views12 pages

Week1-Linked List

A linked list is a data structure where each element, called a node, contains data and a pointer to the next node. This allows dynamic memory allocation and easy insertion/deletion without shifting entries. The document discusses the motivation for linked lists by comparing to arrays, describes the components of nodes, and provides an implementation of a Node class to represent the nodes in a linked list.

Uploaded by

lindytindylindt
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
You are on page 1/ 12

Linked List

Juan Zhai
juan.zhai@rutgers.edu
Motivation
• An array storing integers 1,4, 10, 19, 6. Insert
the integer 7 between the 10 and the 19.
• O(n) for insertion/deletion

• An array has a fixed size.


• Insertion cannot be done if the array is full.
• More space than needed should be allocated
just to be safe.
Juan Zhai, juanzhai@rutgers.edu 2
Linked List
• List of items, called nodes. The order of the nodes
is determined by the address, called the link,
stored in each node. Every node (except the last
node) contains the address of the next node

Hook up units via linking


Allocate units of space on demand
Juan Zhai, juanzhai@rutgers.edu 3
Linked List
• Components of a node
– Info: stores the relevant information, like an integer
– Link: stores the address of the next node
(technical: pointer/reference/address)

• Each node can be allocated anywhere in memory,


unrelated to any previously nodes.
• The links bind the nodes together to provide apparent
contiguity while in fact the nodes are disparate
memory areas
Juan Zhai, juanzhai@rutgers.edu 4
Properties

Juan Zhai, juanzhai@rutgers.edu 8


• Considering the statement current = head;

Juan Zhai, juanzhai@rutgers.edu 9


• Considering current = current.link;

Juan Zhai, juanzhai@rutgers.edu 10


Properties

Juan Zhai, juanzhai@rutgers.edu 11


Review Class/Object
• A class represents the set of properties or
methods that are common to its objects
• An object represents a real-life entity
– All objects share the attributes and the behaviors of
the class
– Values of those attributes are unique for each object

public class Student {


private String name; [”David”, 001]
[”Lucy”, 002]
private int id;
} Juan Zhai, juanzhai@rutgers.edu 12
Implementation
• Class Node
– Represents nodes of a linked list
– It has two instance variables
• Info (of type int, but it can be any other type)
• link (of type Node): a reference to another Node object

public class Node {


private int info;
private Node link;
} Juan Zhai, juanzhai@rutgers.edu 13
Array VS Linked List
Operation Array Linked List
Access Random, single step No random, always start
at the beginning

Insertion/ Need to shift entries No perturbation of


Deletion entries
Storage Allocated in one shot, Allocated only when
drawback of needed, but links need
underestimating/ additional space
overestimating space
Juan Zhai, juanzhai@rutgers.edu 14
Summary
• Comparison between array and linked list
– Operation execution time
– Memory allocation
• Node implementation

Juan Zhai, juanzhai@rutgers.edu 15

You might also like